[BruteForce] 백준 6064: 카잉 달력

6064번: 카잉 달력 (acmicpc.net)

6064번: 카잉 달력

 

code.plus에 BruteForce로 분류되어 있지만 나는 "하나하나 다 대입해가며 따져본다!"는 브루트포스의 원래 의미보다 수학적인 센스가 더 필요한 문제라고 느꼈다.

 

맨 처음 풀 때는 순수하게 하나하나씩 올려가며 테스트했다.

import java.io.*;

public class BOJ_6064 {
    static int M,N;
    static int x,y;
    static int T;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){

            String[] input = br.readLine().split(" ");
            M = Integer.parseInt(input[0]);
            N = Integer.parseInt(input[1]);
            x = Integer.parseInt(input[2]);
            y = Integer.parseInt(input[3]);

            int lastyear = lcm(M,N);
            int tmpX = 1;
            int tmpY = 1;
            int currentYear = 1;


            while(true){
                if(currentYear>lastyear){
                    bw.write("-1");
                    bw.newLine();
                    break;
                }

                if(tmpX==x&&tmpY==y){
                    bw.write(String.valueOf(currentYear));
                    bw.newLine();
                    break;
                }else{
                    if(tmpX<M){
                        tmpX++;
                    }else{
                        tmpX = 1;
                    }
                    if(tmpY<N){
                        tmpY++;
                    }else{
                        tmpY = 1;
                    }

                    currentYear++;
                }
            }

            bw.flush();
        }
    }

    static int lcm(int x, int y){
        int gcd = gcd(x,y);
       // System.out.println("lcm: "+(x*y)/gcd);
        return x*y/gcd;
    }

    static int gcd(int x, int y){
        if(y==0){
            return x;
        }else{
            return gcd(y,x%y);
        }
    }

}

우선 M,N이 주어졌을 때, 카잉 달력은 (M*a+x, N*b+y)에서 (x,y)를 표기하는 것으로 생각해야 한다.(a,b 는 정수)

 

참고로 카잉 달력이 나타낼 수 있는 최대 연도 (M,N)은 M,N의 최소공배수이다. 이 부분을 직관적으로는 파악했는데 논리적으로 풀어 쓰는 건 이상하게 오래 걸렸다. "걍 한 번 돌고 다시 초기화되고 하니까 최대공약수 뭐 아니면 최소공배수... 이런 거 아님?" 하고 직관적으로 파악하는 것과 스스로를 납득시키고 남들에게 설명하기 위해 풀어 쓰는 것에는 상당히 갭이 있다.

 

다시 한 번, 카잉달력으로 표시된 연도 (x,y)가 (M*a+x, N*b+y)의 (x,y)부분이고, 실제 연도가 (M*a+x = N*b+y)가 될 때 그 값이라고 이해하면 되겠다. 따라서 (M,N)년은 (M*a+M, N*b+N)이 되는 해이고 이때 (M(a+1) = N(b+1) = 실제 연도)일 테니까 카잉달력이 나타낼 수 있는 최대 연도는 M,N의 최소공배수이다.

 

따라서 나는 이 문제를 처음 풀 때 위 코드와 같이  최소공배수를 구해 lastYear 변수로 선언하고, while문을 통해 현재 연도인 currentYear를 하나씩 올려 가면서 주어진 규칙에 맞게 (tmpX,tmpY)값을 수정하였다. 그리고 (tmpX,tmpY) = (x,y)가 되면 currentYear를 출력하고, currentYear가 lastYear를 넘어가면 해당 연도는 카잉달력으로 나타낼 수 없다고 판단하여 -1을 출력하도록 하였다.

 

문제는 이 방법으로 풀었을 때 시간 초과가 발생하였다. 근본적으로 뭔가 지름길로 달려갈 수 있는 방법이 있어야겠다고 느꼈는데 내 능력은 딱 여기까지였고..ㅠㅠ 결국 질문란에 있는 힌트를 눈팅했다... 세상에 참 머리 좋은 인간들이 많다고 느꼈다.

 

다시 한 번 생각해 보면,

1. (x,y) = (M*a+x, N*b+y)에서 (x,y)만 쓴 거. 

2. (x,y)년의 실제 연도 : (M*a+x = N*b+y)가 되게 하는 (a,b)값을 찾고, 그 값을 M*a+x, N*b+y에 각각 넣었을 때 나오는 값.

3. 따라서 M*a+x, N*b+y 중 하나가 lastYear(M,N의 최소공배수)를 넘으면 그 연도는 카잉달력으로 출력 불가.

이다.

 

가령 첫 번째 테스트케이스인 10 12 3 9를 보자. 

 

해가 있다고 가정하고, 이 해를 만족시키는 (a,b)를 찾는 것이다. 다시 말해 10*a+3 = 12*b+9를 만족시키는 (a,b)를 찾으면 된다.

 

(a,b) = (0,0)에서 3>2이니까 (0,1)
(a,b) = (0,1)에서 3<21이니까 (1,1),
(a,b) = (1,1)에서 13<21이니까 (2,1),
(a,b) = (2,1)에서 23>21이니까 (2,2),
(a,b) = (2,2)에서 23<33이니까 (3,2). 
(a,b) = (3,2)에서 10*3 + 3 = 12*2+9 = 33.
고로 답은 33이다.

 

생각해 보면 내가 모르고 있던 카잉달력의 속성이 더 있던 것은 아닌데, 나는 "카잉달력의 속성은 이렇다!" 에서 "그러니 해를 찾는 과정은 1씩 하나하나 올려가며 대입하는 것이 아니라, 적절한 a,b를 찾는 것이다!"로 스스로 넘어가지 못했다.

 

이런 결정적인 사고를 하는 능력이 아직 내겐 너무 부족한 것 같다...

 

아무튼 이를 구현한 코드는 아래와 같다. 코드 첨부하고 마친다.

import java.io.*;

public class BOJ_6064_2 {
    static int M,N,x,y;
    static int T;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            String[] input = br.readLine().split(" ");

            M = Integer.parseInt(input[0]);
            N = Integer.parseInt(input[1]);
            x = Integer.parseInt(input[2]);
            y = Integer.parseInt(input[3]);

            int a = 0;
            int b = 0;
            int lastyear = lcm(M,N);
            while(true){
                if(M*a+x>lastyear||N*b+y>lastyear){
                    bw.write("-1");
                    bw.newLine();
                    break;
                }

                if(M*a+x == N*b+y){
                    bw.write(String.valueOf(M*a+x));
                    bw.newLine();
                    break;
                }

                if(M*a+x<N*b+y){
                    a++;
                }else{
                    b++;
                }
            }
            bw.flush();
        }

    }

    static int lcm(int x, int y){
        int gcd  = gcd(x,y);
        return x*y/gcd;
    }

    static int gcd(int x, int y){
        if(y==0){
            return x;
        }else{
            return gcd(y,x%y);
        }
    }
}