BOJ 6064. 카잉 달력

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

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y> 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N> 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

1. 문제 해석

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

• 첫 번째 해는 <1:1>, 두 번째 해는 <2:2>이다. -> <M,M> -> <1,M+1>
• <x:y>의 다음 해는 <x':y'> 이다.
• x < M 이면 x' = x + 1, 아니면 x' = 1
• y < N 이면 y' = y + 1, 아니면 y' = 1
• M, N, x, y가 주어졌을 때, <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;
}