6064 카잉 달력

6064 카잉 달력 (c++)

문제

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

접근 방식

최소공배수, 수학 결국 우리나라 육십갑자처럼 돌아가면서 짝을 이루는 숫자를 구하는건데, 숫자 N에 대하여 두 M과 N의 나머지가 X와 Y로 떨어지는 수를 구하는 문제 (최소공배수까지만 돌리면 되지만 N * M까지 돌려도 시간복잡도에 문제가 없어보였다)

문제 풀이

#include <iostream>
#define endl '\n'
using namespace std;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T, M, N, X, Y;
    
    cin >> T;

    while (T--)
    {
        cin >> M >> N >> X >> Y;
        bool find = false;
        int result;
        for (int i = 0; i <= N; ++i)
        {
            result = X + (M * i);
            if (N == Y)
            {
                if (result % N == 0)
                {
                    find = true;
                    break;
                }
            }
            else
            {
                if (result % N == Y)
                {
                    find = true;
                    break;
                }
            }
        }
        if (find) cout << result << endl;
        else cout << -1 << endl;
    }
    return 0;
}

다시 생각해볼 점

1. X:Y로 1씩 더해가며 풀었지만 O(N^2)으로 N이 40’000이었기 때문에 1,600,000,000 이라 당연히 실패
2. 생각해보니 어떤 수 I을 M과 N으로 나누었을 때 나머지가 X와 Y면 되는게 아닌가 생각이 들었고
3. 그렇다면 이미 X는 맞았다는 가정하에 i가 0~N(NM)까지 X에 iM을 더한 숫자를 N으로 나눴을 때 나머가 Y면 된다는 생각을 하게 됨
4. 그런데 이 때 놓친게 “최소값일 경우”에서 알 수 있는 N == Y 인 경우이다. (1, 1, 1, 1)
5. 결국 질문게시판에서 반례를 보고 해결책이 생각나 풀었지만 실제 문제에서는 이걸 내가 직접 생각해내야한다.
6. N == Y 일때는 나머지가 Y 가 아닌 0이 된다는 점을 스스로도 생각해 낼 수 있어야 하겠다.