[백준/C++] 6064 - 카잉 달력

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

구현하기

문제 로직을 살펴보면 <x:y>는 다음과 같이 변한다. x는 쭉 늘어나다가 M이 되면 그 다음에 1로 변하고, y도 마찬가지로 쭉 늘어나다가 N이 되면 그 다음에 1로 변한다.

즉 k번째 해에서
x = ((k - 1) % m) + 1
y = ((k - 1) % n) + 1
이다.

-> 나머지를 이용해야 되는 문제다!

주어진 <x:y>가 몇번째 해인지를 구하려면
일단 x부터 for문을 시작한다. 위의 x 식을 변형하면 k는 x로 나누었을 때 나머지가 m이어야 한다. 따라서 k에 m씩 더해준다. k는 최대공배수인 m * n 까지 증가시켜준다.

이때 for문 안에서는 y = ((k - 1) % n) + 1 인지를 검사해주면 된다. 해당 식을 만족하는 경우, 현재 인덱스 k를 answer에 저장해두고 for문을 탈출한다.

전체 코드

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int m, n, x, y;
        cin >> m >> n >> x >> y;

        int answer = -1;

        for (int k = x; k <= m * n; k += m) {
            if ((k - 1) % n + 1 == y) {
                answer = k;
                break;
            }
        }

        cout << answer << endl;
    }

    return 0;
}