[BOJ 6064 C++] 카잉 달력

6064번: 카잉 달력

문제 분석

• 시간 제한 1초 : 약 1억 연산
  약 16억의 모든 정수를 탐색 할 수는 없음
• 세상의 종말이 도래하는 연도 : <M,N> : M,N의 최소공배수번째 연도
• x,y의 의미 
  k % M = x, k % N = y (단, x,y가 0일때 x,y는 각각 M,N)
• <a,b> 가 주어진 경우 : k % M = a 일 때, k % N = b 인 경우를 찾으면 됨

풀이 방식

• x,y가 주어지면 x에 M씩 더해가며 ( 항상 나머지가 x가 되도록 ) 반복한다.
• x에 M을 더한 값을 N 으로 나눈 나머지가 y인 경우 그때의 값을 출력한다.
• M,N의 최소공배수까지 탐색했는데 요구하는 값이 나오지 않을 경우 -1을 출력한다.

#include <iostream>

using namespace std;

int t, m, n, x, y, l, tmp;
bool exist;

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::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> m >> n >> x >> y;
        l = lcm(m, n);
        exist = false;
        for (int i = x; i <= l; i += m) {
            (i % n == 0) ? tmp = n : tmp = i % n;
            if (tmp == y) {
                cout << i << '\n';
                exist = true;
                break;
            }
        }
        if (!exist) cout << -1 << '\n';
    }
    return 0;
}

느낀 점

• a%b == (a+b)%b 라는 간단하고 기본적인 개념을 이용하면 되는데 이 아이디어가 떠오르지 않아 시간이 오래걸렸다.
• 그래도 한계가 최소공배수라는 점은 쉽게 찾았다.
• 아이디어를 떠올리고 찾아내는게 구현보다 훨씬 어려운 문제였다.

시간 복잡도(각 테스트케이스 마다)

• 최소공배수 구하기 : O(logn)
• k 찾는 반복문 : O(M*N / M ) = O(N)
  ➣ O(N)