[백준] 6064번: 카잉 달력 - JAVA

문제 링크

BOJ 6064번: 카잉 달력

6064번: 카잉 달력

풀이 과정

아 문제의 핵심은 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다.

 

예를 들어,

# <10, 12>일 때
1번째 해 : <1, 1>
2번째 해 : <2, 2>
...
10번째 해 : <10, 10>
11번째 해 : <1, 11>
12번째 해 : <2, 12>
13번째 해 : <3, 1>

이 처럼 x가 M, y가 N에 도달할 경우 1로 변경된다는 것이다.

단순히 하나씩 계산하며 만족하는 결과를 찾는다면, 최악의 경우 O(NM)의 시간복잡도를 갖게 된다.

문제를 풀기 위한 아이디어는 x와 y의 값은 구하고자하는 해에서 M과 N으로 나눈 나머지라는 것이다.

 

예를 들어

<10, 12>
1번째 해 : <1, 1>
2번째 해 : <2, 2>
3번째 해 : <3, 3>
...
13번째 해 : <3, 1>
...
23번째 해 : <3, 11>

즉, 3, 13, 23번째 해 등 M의 배수(n>=0)에서 3만큼 더한 해가 지나야 3이 나온다는 것을 의미한다.

 

모든 경우를 다 구하며 계산할 수는 없으므로 x값을 기준으로 y의 값 또한 N으로 나눈 나머지가 y가 나오는지를 확인하면 된다.

구할 수 있는 최대 범위의 경우 M과 N의 최소공배수인데 이를 초과하게 되면 예외상황이기 때문에 'error'를 출력하면 된다. 최소공배수는 유클리드 호제법으로 구하였다.

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int M = sc.nextInt(), N = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();

            int lcm = M * N / gcd(M, N);
            int n = 0;
            int ans = -1;
            while (n * M < lcm) {
                if ((n * M + x - y) % N == 0) {
                    ans = n * M + x;
                    break;
                }
                n++;
            }

            System.out.println(ans);
        }
    }

    static int gcd(int n1, int n2) {
        if (n2 == 0)
            return n1;
        return gcd(n2, n1 % n2);
    }
}

 

제출 결과