[Python] 백준 6064번 - 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 수학
 - 정수론
 - 중국인의 나머지 정리

 

문제

최근에 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을 출력한다.

---

 

예시로 나온 <10:12> 의 값을 보고

 

처음엔 60갑자 구하듯이 구해보면 되겠다. 쉽겠다 싶었다.

 

하지만 나는 60갑자도 계산할 줄 몰랐고 그에 응용한 이 문제는 더욱이 풀 수가 없었다.

 

 가만히 생각해보다 일단 적어보자 하고 일단 10:12 일 때 순서를 하나하나 다 적어봤다

 

1 - 1 1
2 - 2 2
3 - 3 3
4 - 4 4
5 - 5 5
6 - 6 6
7 - 7 7
8 - 8 8
9 - 9 9
10 - 10 10
11 - 1 11
12 - 2 12
13 - 3 1
14 - 4 2
33 - 3 9

일단 적다 보니 알아낸 것

• 작은 숫자가 한 바퀴 도는 것을 기준으로 하면 되겠다.
• 맨 처음 10과 12의 차이만큼 2의 약수, 배수만큼 간격이 벌어져있다.
• 수학적인 공식이 있을 것 같다.

이중에 다시 생각해보니 규칙이라고 부를만한 게 하나도 없었다.

 

그나마 3번째 '수학적인 공식이 있을 것 같다'였다.

 

그래서 난 점화식을 찾기 위해 노력해 보고

 

혹시 DP문제인가 싶어서 건드려봤으나 여전히 아닌 것 같았다.

 

그래서 알고리즘 분류에 있던

 

'중국인의 나머지 정리'에 대해서 검색해 보았다.

 

https://ko.wikipedia.org/wiki/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%A0%95%EB%A6%AC

중국인의 나머지 정리 - 위키백과, 우리 모두의 백과사전

 

요점은 

 

x % 3 = 2

x % 5 = 3

x % 7 = 2

 

x = ?

을 찾는 방법인데

 

솔직히 잘 모르겠다.

 

그래서 결국 검색해 보았다.

 

import sys
input = sys.stdin.readline

t = int(input())

def find(m, n, x, y):
  while x <= m*n:
    if (x-y)%n == 0:
      return x
    else:
      x += m
  return -1

for _ in range(t):
  m, n, x, y = map(int, input().split())
  print(find(m, n, x, y))

 

위의 내가 찾은 규칙성과는 상관없는 수식의 코드가 만들어졌다.

 

예를 들어 앞선 예시의 

 

13 11 5 6 = 83을 찾아보도록 하자.

 

m = 13, n = 11, x = 5, y = 6

 

1. (5-6) % 11 = 10 / x = 5 + 13 = 18

2. (18-6) % 11 = 1 / x = 18 + 13 = 31

3. (31 - 6) % 11 = 3 / x = 31 + 13 = 44

4. (44 - 6) % 11 = 5 / x = 44 + 13 = 57

5. (57 - 6) % 11 = 7 / x = 57 + 13 = 70

6. (70 - 6) % 11 = 9 / x = 70 + 13 = 83

7. (83 - 6) % 11 = 0 / x = 83

 

위와 같은 과정을 겪게 된다.

 

10 12 7 2 의 경우

 

위의 과정을 계속해서 찾다가 m * n 의 범위인 120을 넘어버려서 -1이 리턴되었다.