[백준 6064] 카잉 달력

🔗알고리즘 문제

중국인의 나머지 정리라는 처음 보는 이론이 등장하여 공부해보았지만 알고리즘에 적용시키기는 힘들었다.. 고민고민하다 힌트를 보았는데 굳이 중국인의 나머지 정리를 사용하지 않더라도 해결할 수 있다는 말을 듣고 생각보다 싱겁게 해결하였다. 사고가 갇히지 않고 좀 더 다양한 방면에서 문제를 볼 수 있는 능력을 길러야겠다.

문제 분석

이 문제는 카잉 달력의 마지막 해와 현재 해가 주어질 때 현재는 몇번째 해인지 알아내는 문제이다.

카잉 달력은 <x:y> 형식으로 표현되는 달력을 말하는데, 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 달력의 마지막 해이다.

발상 & 알고리즘 설계

이 문제는 굳이 중국인의 나머지 정리를 사용하지 않더라도 간단하게 구현할 수 있는 문제이다.

간단한 예제를 통하여 이를 증명할 수 있다.

m : 10이고 n : 12라고 할 때 51번째 해를 x:y로 표현하고자 한다면 최댓값으로 나눈 나머지로 표현할 수 있다.

51은 m이 5번 들어가고 1해가 더 지나야 하므로 x는 1이 된다. 똑같은 방법으로 n이 4번 들어가고 3해가 더 지나야 하므로 y는 3이 된다.

거꾸로 x가 1이고 y가 3일 때 해를 구한다고 하면, x가 1이 되는 해에서 y값을 구한 후 구하려는 y와 같은지 비교하면 됩니다.

m이 10이므로 x가 1인 경우는 1 11 21 31 41 51...

이 중 y값이 구하려는 y와 같은 해는 51로 답을 구할 수 있다.

코드

#include<iostream>

using namespace std;

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b){
    return (a * b) / gcd(a, b);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t;

    cin >> t;

    while(t--){
        int m, n;
        int x, y;

        cin >> m >> n >> x >> y;

        int result = -1;
        int max = lcm(m, n);

        for(int i = x; i <= max; i += m){
            int tempY = i % n;
            if(tempY == 0){
                tempY = n;
            }

            if(tempY == y){
                result = i;
                break;
            }
        }

        cout << result << "\n";
    }
}