BOJ 6064. 카잉 달력

• 문제링크 : https://www.acmicpc.net/problem/6064

---

문제 요약

카잉 달력은 해를 <x:y>로 나타낸다. 첫 해는 <1:1>이고, 해가 바뀔 때마다 x와 y가 각각 1씩 늘되 x가 M을, y가 N을 넘으면 1로 돌아간다. 마지막 해는 <M:N>이다. 예를 들어 M = 10, N = 12이면 <3:1>은 13번째 해이고 <10:12>는 60번째 해다. M, N, x, y가 주어질 때 <x:y>가 몇 번째 해인지 구하고, 그런 해가 없으면 -1을 출력한다.

---

1. 문제 해석

이전에 풀었던 E S M 문제와 같지면 여기에서는 날짜가 두 개 밖에 없다. M과 N보다 작거나 같은 두 자연수 x, y를 이용해서 년도를 로 표현한다

• 첫 번째 해는 <1:1>, 두 번째 해는 <2:2>이다. -> <M,M> -> <1,M+1>
• 의 다음 해는 <x':y'> 이다.
• x < M 이면 x’ = x + 1, 아니면 x’ = 1
• y < N 이면 y’ = y + 1, 아니면 y’ = 1
• M, N, x, y가 주어졌을 때, 이 몇 번째 해인지 구하는 문제
• 1 ≤ M, N ≤ 40,000 -> 전체 경우의 수는 MxN = 16억 너무 많다. -> 건너뛰면서 브루트 포스 실행

• M = 5, N = 7

• 1: <1,1>     • 10: <5,3>     • 19: <4,5>     • 28: <3,7> • 2: <2,2>     • 11: <1,4>     • 20: <5,6>     • 29: <4,1> • 3: <3,3> • 12: <2,5>     • 21: <1,7>     • 30: <5,2> • 4: <4,4>     • 13: <3,6> • 22: <2,1>     • 31: <1,3> • 5: <5,5>     • 14: <4,7>     • 23: <3,2>     • 32: <2,4> • 6: <1,6>     • 15: <5,1>     • 24: <4,3>     • 33: <3,5> • 7: <2,7>     • 16: <1,2>     • 25: <5,4>     • 34: <4,6> • 8: <3,1> • 17: <2,3>     • 26: <1,5>     • 35: <5,7> • 9: <4,2>     • 18: <3,4>     • 27: <2,6>

예를 들어, <3,6>을 찾는다고 했을때, M을 기준으로 하면 <3,3> 부터 5를 더한 <3,1>, 그리고 5를 더하여 <3,6>와 같이 찾을 수 있다. 3에서 5씩 건너뛰면서 실행하면 세 번 만에 <3,6>을 찾을 수 있다. 그리고 N을 기준으로 하면 <1,6>부터 7을 더한 13번째의 수 <3,6>을 찾을 수 있다.

여기에서 <x,y>는 <k%M, k%N> 과 같다는 것을 알 수 있다.

---

2. 문제 풀이

<x,y>는 <k%M, k%N> 과 같다. 여기서 나머지 연산값이 0이 되지 않도록 해주기 위해서 x와 y에 미리 1씩 빼주어야 한다. 그리고 정답을 출력할 때 1을 다시 더해준다. <(k-1)%M + 1, (k-1)%N + 1>

#include <iostream>
using namespace std;
int main() {
    int t, m, n, x, y;
    cin >> t;
    while (t--) {        
        cin >> m >> n >> x >> y;
        x -= 1; y -= 1;
        bool isFound = false;
        for (int k=x; k<(n*m); k+=m) {	// x부터 m씩 건너뛰며
            if (k%n == y) { 		// n자리의 나머지 연산값이 y라면 일치
                cout << k+1 << endl;
                isFound = true;
                break;
            }
        }
        if (!isFound) cout << -1 << endl; // 찾지 못했다면 -1 출력
    }
    return 0;
}