[백준 알고리즘] 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력
이 문제는 스스로 푼 문제는 아니므로 강의를 듣고 푼 내용을 정리한다.

이 문제에서 <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다.. 이 조건이 있기 때문에 나머지 정리를 이용해서 x 나 y 중 하나를 고정시킬 수 있다. 위 조건을 만족하는 모든 경우의 수에서 1을 빼주게 되면 x에 들어가는 값은 0...M-1 이 반복되고, y에 들어가는 값은 0...N-1 이 반복된다. 따라서 i 번째 해에 대한 x의 값은 i * M + 3 로 고정 시킬 수 있다. 그럼 이제 N 자리에 y 값을 가지는 i 번째 해만 검사해보면 된다. i 에 M씩 계속 더해주면 나머지가 x 인 값이 계속해서 나오기 때문에 값을 계속 증가시키면서 y값이 i % N 가 되는 i를 구한다.

풀이

코드

#include <iostream>

using namespace std;

int main (){
    int T;
    scanf("%d", &T);

    while(T--){
        int M, N, x, y;
        scanf("%d %d %d %d", &M, &N, &x, &y);

        // 나머지를 맞추기 위해 1씩 빼준다.
        x -= 1;
        y -= 1;

        // i 는 M으로 나눈 나머지가 x가 되는 수 -> x를 M으로 가지는 해
        int i;
        for (i = x; i < (M*N) ; i += M){
            // M 과 N 이 모두 일치해야 하기 때문에 i를 N으로 나눴을 때 나머지가 y가 되는 해을 찾는다. -> y를 N으로 가지는 해
            if (i % N == y){
                printf("%d\n", i+1); // 다시 1을 더해주어야 실제 값이 나온다.
                break;
            }
        }

        // 정답을 찾지 못한 경우
        if (i >= (M*N)){
            printf("-1\n");
        }
    }
}