6064번: 카잉 달력 (백준 온라인 저지, C++)

문제 풀이

 

 이 문제는 단순히 구현을 했을 때는 시간 초과가 나게 됩니다. 따라서 x를 고정시켜 주고, 이 x에 따라 나올 수 있는 y를 찾아가면서 문제를 풀어야 합니다.

 

 예를 들어, 10 12 3 9의 경우 3이 x의 자리에 올 때 y의 자리에 올 수 있는 값은 3, 1, 11, 9, ... 이며 이 때 각각 10년의 텀을 두고 발생하게 됩니다. 따라서 답은 3년에 3*10을 더한 33년이 됩니다. 주의할 점은 % 연산의 경우 0부터 시작하기 때문에 이를 고려하여 코드를 구성해야 합니다.

 

 만약 가장 처음에 y 자리에 왔던 값이 다시 나타나게 된다면, 이는 한 주기를 모두 지났다는 뜻이 되므로 종말 년도를 넘어섰다는 뜻이 됩니다. 따라서 -1을 출력합니다.

 

 또는 최소 공배수와 최대 공약수를 활용하여 종말 년도를 먼저 계산하고, 이를 넘어서는 경우를 찾아주는 것도 가능합니다.

 

 

코드

 

#include <iostream>
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
 
        int ans = x, b = (x - 1) % n + 1;
        int tmp = b;
 
        while (1)
        {
            if (b == y)
                break;
            
            b = (b + m - 1) % n + 1; 
            ans += m;
 
            if (tmp == b)
            {
                ans = -1;
                break;
            }
        }
 
        cout << ans << "\n";
    }
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력