[백준]6064-카잉 달력

문제는 위와 같다.

#include <iostream>
using namespace std;
 
int gcd(int n, int m);
int lcm(int n, int m);
 
int main()
{
    int repeat;
    cin >> repeat;
    for (int k = 0; k < repeat; k++) {
        int M, N, x, y;
        cin >> M >> N >> x >> y;
        if (M < N) {
            int tmp = M; M = N; N = tmp;
            tmp = x; x = y;    y = tmp;
        }
        int least = lcm(M, N) / M;
        int point = -1;
 
        for (int i = 0; i < least; i++) {
            int num = (i * M + x) % N == 0 ? N : (i * M + x) % N;
            if (num == y) {
                point = i * M + x;
                break;
            }
        }
        cout << point << endl;
    }
}
 
int gcd(int n, int m) {
    if (m == 0)
        return n;
    else
        return gcd(m, n % m);
}
int lcm(int n, int m) {
    return n * m / gcd(n, m);
}

 

일단 답은 위와 같고..

 

일단 M과 N으로 주어진 수의 최소공배수를 구해야한다.

그 이유는 M과 N으로 구성되는 달력의 최대 날짜를 먼저 구해야 반복 횟수를 알 수 있기 때문.

최소공배수를 구하려면 최대공약수를 구해야하고, 그건 구글링을 통해 알아보면 금방이다.

 

여튼 내가 사용한 방법은 x를 고정한 다음 따라오는 y를 구하면서 비교하는 방법이다.

코드를 보면 금방 이해할 수 있다.

 

처음에는 M과 N을 알면 어떤 x와 y가 들어오더라도 바로 찾을 수 있도록 2차원 배열을 동적으로 만들었는데, 메모리 초과가 나와서 그냥 매번 구하는 방법으로 바꿨다...