[solved.ac CLASS 3] 백준 6064 카잉달력

위의 문제는 브루트포스로 풀려고 하면 무조건 시간초과가 뜬다.

마지막 해는 M 과 N 의 LCM 이다. M 과 N 이 소수라면 그 크기는 대략적으로 40000 * 40000 정도가 되니

이는 1초이상의 결과가 나온다. 따라서 다른 방법을 생각해 봐야 한다.

 

 

핵심 :

1. 위 문제에서 우리가 구하고자 하는 년도를 k 로 둔다.

2. (k - x) % M == 0, (k - y) % N == 0 이다.

(위의 2번의 유도는 아래의 사진을 첨부한다.)

3. k 를 M 만큼 증가시키면 그 나머지는 계속 x 를 유지한다.(k % M == x 일 때 (k + M) % M == x 이다)

위의 3번 방식으로 지속적으로 k 를 M 만큼 증가시키면 LCM(M, N) / M 정도의 big O 를 가지므로 시간제한에 안걸릴 수 있다.

소스코드

#include <iostream>
#include <vector>

using namespace std;

int T, M, N, x, y;

int GCD(int a, int b){
    if(a % b == 0) return b;
    return GCD(b, a % b);
}
int LCM(int a, int b){
    return (a * b) / GCD(a, b);
}

int main(void){
    
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> M >> N >> x >> y;
        int dtryYear = LCM(M, N);
        int k = x;
        while (true) {
            if((k - x) % M == 0 && (k - y) % N == 0) break;
            if( k > dtryYear ){
                k = -1;
                break;
            }
            k += M;
        }
        cout << k << '\n';
    }
    
    
    return 0;
}