[백준/Python]6064: 카잉 달력

문제

https://www.acmicpc.net/problem/6064
백준 문제집 - 0x12강 - 수학

 

알고리즘: 수학, 브루트포스, 정수론

---

풀이

최근에 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

일일히 계산해서 구하면 시간초과다.

규칙을 파악해보면 다음과 같다.
K년을 카잉 달력으로 표시하면 (K % M) : (K % N) 이 된다.
단, K가 M이나 N과 같은 값일 경우 위 식에 대입하면 0이 반환되지만 실제로는 M, N에 해당되는 값으로 표현해야한다.

예를들어 M = 10, N = 12이고 K = 10일때를 생각해보자.
K % M = 0, K % N = 2이므로 예상한 결과값은 0 : 2 다.
하지만 조건을 보면 현재 해 x를 기준으로 다음 해 x'를 표현한다.
다시 말해 이전 해가 M or N 보다 작으면 x' = x + 1로 표현하고, 같거나 크다면 1로 바꿔주는것이다.

 

10 같은경우 이전 해 9가 M보다 작으니 그대로 10으로 표현하고, 11은 이전 해 10이 M과 같으므로 1로 표현한다.

문제에선 K가 아닌 카잉달력으로 표현된 x : y가 주어지고, 이를 K로 변환해야한다.

x 또는 y를 기준으로 삼고 나머지 한 쪽을 탐색하는 과정을 진행한다.
카잉달력으로 변환하는 식은 (K % M) : (K % N)이므로, K % M = x, K % N = y가 되어야한다.
따라서 K가 x, y를 모두 만족하려면 1) x로 시작해서 M 간격으로 증가, 2) y로 시작해서 N 간격으로 증가해야한다.
즉, K - x가 M의 배수, K - y가 N의 배수여야 하는것이다.

 

전체 코드

# 메모리: 32544KB / 시간: 4448ms
from sys import stdin


input = stdin.readline

T = int(input())

for _ in range(T):
    M, N, x, y = map(int, input().split())

    k = x
    while k <= M * N:
        # k % M == x 와 같이 작성하면 k == M 일때를 처리하지 못함.
        if (k - x) % M == 0 and (k - y) % N == 0:
            print(k)
            break

        k += M
    else:
        print(-1)

 

예제 1의 데이터를 바탕으로 진행해보면 아래와 같다.

M, N, x, y = 10, 12, 3, 9

# k = x
k = 3

# 1) k = 3
(k - x) % 10 = 0
(k - y) % 12 = 6
k += 10

# 2) k = 13
(k - x) % 10 = 0
(k - y) % 12 = 1
k += 10

# 3) k = 23
(k - x) % 10 = 0
(k - y) % 12 = 2
k += 10

# 4) k = 33
(k - x) % 10 = 0
(k - y) % 12 = 0
break

검증해보면 k % M = 3, k % N = 9 로 x, y값을 만족한다.

 

이모티콘 받은김에 넣어봤다.