[백준] 6064번 카잉 달력 해설 및 풀이 (Python)

백준 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>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

 

---

 

문제 유형

수학

브루트포스 알고리즘

정수론

중국인의 나머지 정리

 

풀이 방법 도출

 

카잉 제국의 달력은 두 개의 자연수 M과 N을 주기로 하는 형식을 가집니다.
각 연도는 <x:y> 형식으로 표현되며, 특정 연도 이후의 해는 다음과 같이 결정됩니다.

 

• x < M이면 x' = x + 1, 그렇지 않으면 x' = 1
• y < N이면 y' = y + 1, 그렇지 않으면 y' = 1

 

따라서 이 문제를 해결하는 가장 효율적인 방법은 수를 순환시키면서 탐색하는 것입니다.

 

1. (x, y)가 되는 k를 찾으려면, (x, y)를 만족하는 가장 작은 k를 구해야 합니다.
2. k는 x에서 시작하여 M만큼 증가하는 수열을 따릅니다.
3. k가 y와 일치하는지 확인하면서 진행합니다.
4. 최대 M * N까지만 탐색하고, k % N == y가 성립하는지 검사합니다. 맞다면 k + 1을 출력하고, 일치하지 않으면 -1를 반환합니다.

 

 

시간 복잡도

• k는 x, x+M, x+2M, ...의 형태로 증가하며 최대 M * N번까지 반복할 수 있습니다.
• 하지만 M씩 증가하는 패턴이므로 최악의 경우 N번 반복 (O(N))

 

---

 

문제 코드

import sys  # 표준 입력을 빠르게 처리하기 위한 sys 모듈 사용


# 첫 줄에서 테스트 개수 T 입력 받음
t = int(sys.stdin.readline())


# T개의 테스트 케이스 처리
for _ in range(t):
    # M, N, x, y 값 입력
    m, n, x, y = map(int, sys.stdin.readline().split())


    x -= 1
    y -= 1


    # k 값을 x에서 시작하여 M씩 증가시키며 찾음
    k = x
    while k < m * n:  # 최대 M * N번만 탐색
        if k % n == y:  # y 조건을 만족하면 출력
            print(k + 1) 
            break
        k += m  # k를 M만큼 증가시키며 탐색
    else:
        print(-1)  # 유효한 해가 없는 경우 -1 출력