[Baekjoon] 6064 - 카잉 달력

📝 문제

 

 

🔑 풀이 과정

· 해를 표현하는 방식이 <x:y>일 때, x는 1부터 M까지를 계속 순환하고, y는 1부터 N까지를 계속 순환한다.

 

· 다음표는 M = 10, N = 12일때의 해 변화를 나타낸 것이다. 초록색 축이 몇번째 해인지를 나타내는 값이다.

만약 <4:2>가 몇 번째 해인지 알고싶다면? 10a+4, 12b+2를 만족하는 숫자를 찾으면 된다.(a, b는 자연수)

거꾸로 생각하면 (n-4) % 10 == 0, (n-2) % 12 == 0 을 만족하는 n을 찾으면 되는것이다.

 

· 그리고 <M:N>이 달력의 마지막 해라고 나와있는데, 즉 M과 N의 최소공배수일때가 마지막 해가 된다.

 

· 최소공배수를 구하는 방법은, 유클리드 호제법을 사용해서 최대공약수를 구한 뒤, 두 수의 곱을 최대공약수로 나누면 그게 최소공배수다. 자세한건 검색! 여기서는 더 자세히 다루지 않겠다.

 

· 처음에는 j를 1부터 M,N의 최소공배수까지 돌리면서 (j-x) % M == 0, (j-y) % N == 0 인 경우를 찾았다. 그러나 이렇게 푸는 방식은 (당연하게도) 수가 커지면 범위가 너무 넓기때문에 시간초과가 발생한다. (무한루프 돌때의 경우도 "시간 초과"가 아닌 "틀렸습니다"가 나오므로 참고). 탐색 범위를 좁혀서 시간을 더 줄여야 한다!

 

· 그래서 풀이 방식을 좀 더 바꿔봤다. x나 y중 원하는 값 하나가 나오는 상황을 고정시키고, 나머지 값도 만족시키는 상황을 찾으면 되는것이다! 좀 말이 어려운데, 위의 표를 보면 x가 4일때는 4번째해, 14번째해 ... 이런식으로 해가 10n + 4(n은 0부터)로 고정되어 있다. 이 10n + 4를 가지고 (10n + 4) -2 % 12 == 0을 만족시키는 값을 찾아주면 된다. 10n + 4가 M, N의 최소공배수를 넘지 않는 범위에서만 찾아주면 된다. 그러면 앞선 방법에서는 14번을 반복해야 답을 찾을 수 있었지만, 지금 방법에서는 2번만 반복해도 답을 찾을 수 있다.(n=0인 4번째 해, n=1인 14번째 해 총 2번)

 

· 만약 오답이 나온다면 해당 반례를 돌려보자

15
40000 39999 39999 39998
40000 39999 40000 39999
40000 40000 40000 39999
40000 39998 40000 39997
39999 2 39998 2
3 40000 3 39999
40000 3 40000 3
8 2 4 2
10 12 2 12
12 10 12 10
12 10 1 1
12 6 12 6
10 1 5 1
1 10 1 5
1 1 1 1

답:
1599959999
1599960000
-1
-1
39998
39999
120000
4
12
60
1
12
5
5
1

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        //입력
        int T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수

        for(int i = 0; i < T; i++){ //테스트 케이스의 수 만큼 반복
            st = new StringTokenizer(br.readLine());
            long M = Long.parseLong(st.nextToken());
            long N = Long.parseLong(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            //M과 N의 최대공약수 구하기
            long gcd = 0;
            if(M >= N){
                gcd = getGcd(M, N);
            }
            else{
                gcd = getGcd(N, M);
            }

            long lcm = M * N / gcd; //M과 N의 최소공배수 구하기

            long j = 0;
            for(j = 0; (M * j) + x <= lcm; j++){
                if((((M * j) + x) - y) % N == 0){
                    break;
                }
            }

            if(lcm <(M * j) + x){
                sb.append(-1).append("\n");
            }
            else{
                sb.append((M * j) + x).append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static long getGcd(long m, long n){
        if((m % n) != 0){
            return getGcd(n, (m % n));
        }
        else{
            return n;
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 정수론

- 중국인의 나머지 정리