6064번: 카잉 달력

문제

카잉 제국의 달력은 두 개의 수 <M:N>을 이용하여 연도를 표기합니다. 첫 번째 해는 <1:1>, 두 번째 해는 <2:2>로 표현됩니다. <x:y>의 다음 해는 <x':y'>로 표현되는데, 만약 x < M 이면 x' = x + 1 이고, 그렇지 않으면 x' = 1이 됩니다. y에 대해서도 동일한 규칙이 적용됩니다. 네 개의 정수 M, N, x, y가 주어질 때, <x:y>가 카잉 달력의 몇 번째 해를 나타내는지 구하는 프로그램을 작성하는 문제입니다. 만약 유효하지 않은 연도라면 -1을 출력합니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스는 M, N, x, y (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)로 구성됩니다.
• 출력: 각 테스트 케이스에 대해 유효한 해라면 몇 번째 해인지 출력하고, 유효하지 않은 표현이라면 -1을 출력합니다.

풀이: 0-based Index와 배수 점프(Jump)를 활용한 탐색 최적화

M과 N의 크기가 최대 40,000이므로, 정답이 될 수 있는 최대 연도는 16억(40,000 * 40,000)에 달할 수 있습니다. 이를 1부터 1씩 증가시키며 완전 탐색하면 무조건 시간 초과가 발생합니다. 따라서 수학적 성질을 이용하여 특정 조건을 만족하는 연도만 건너뛰며(Jump) 탐색하는 최적화가 필수적입니다.

• 인덱스 보정 (0-based Index): 주어진 x와 y에서 1을 빼주어 0부터 시작하는 인덱스로 치환합니다. 이렇게 하면 문제의 복잡한 순환 규칙이 프로그래밍의 모듈러(%) 연산과 완벽하게 일치하게 됩니다.
• 배수 점프 (건너뛰기 탐색): 우리가 찾는 정답 연도 i는 i % M == x와 i % N == y를 동시에 만족해야 합니다. 탐색을 시작할 때 초기값을 i = x로 두고, 한 번 탐색할 때마다 1이 아닌 M 단위로 점프(i += m)합니다. 이렇게 하면 만들어지는 모든 i는 항상 i % M == x 조건을 자연스럽게 만족하므로, 우리는 i % N == y 조건만 확인하면 됩니다. 이를 통해 탐색 횟수가 기하급수적으로 줄어듭니다.
• 종료 조건 및 예외 처리:
  • 정답 발견: i % n == y를 만족하는 순간, 0-based로 계산했던 연도 i에 1을 다시 더해주어(i + 1) 출력하고 즉시 탈출합니다.
  • 탐색 상한선: 두 달력이 다시 맞물려 <1:1>로 돌아오는 시점은 M과 N의 최소공배수(LCM)입니다. 최악의 경우인 두 수의 곱 M * N까지만 탐색하도록 상한선을 정해주면 무한 루프를 방지할 수 있습니다. 끝까지 탐색했음에도 찾지 못했다면 유효하지 않은 연도이므로 -1을 출력합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            
            // 모듈러 연산을 위해 0-based 인덱스로 치환
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            boolean flag = true;
            
            // i를 x부터 시작하여 m씩 건너뛰며 탐색 (i % m == x 는 항상 참이 됨)
            for (int i = x; i < m * n; i += m) {
                // 남은 조건인 i % n == y 를 만족하는지 검사
                if (i % n == y) {
                    bw.write((i + 1) + "\n"); // 정답 출력 시 다시 1을 더해 복원
                    flag = false;
                    break;
                }
            }

            // 끝까지 찾지 못했다면 유효하지 않은 표현이므로 -1 출력
            if (flag) {
                bw.write("-1\n");
            }
        }

        bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 정수론 (Number Theory), 중국인의 나머지 정리 (Chinese Remainder Theorem) 개념 응용