[백준BOJ] 6064번 카잉 달력.py

 

백준 저지에서 카잉 달력을 파이썬을 통해 풀어 보았다. 

 

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

6064번: 카잉 달력

 

 

6064번 카잉 달력.py

tomy9729/Algorithm

 

 

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

설명

x와 y를 1씩 증가시키면 문제를 해결하려고 한다면 당연하게도 시간 초과에 걸린다.

 

카잉 달력의 마지막은 m과 n의 최소 공배수이다. 파이썬에서 제공하는 최대 공약수 gcd를 통해 최소 공배수를 구할 수 있다. 

 

x만을 기준으로 x만 찾는다고 하면 1씩 증가하여 찾을 때보다 m배만큼 빠르게 찾을 수 있다. 주어진 x에 대해서 반복문을 통해 m만큼 증가시키며 찾은 x에 대해 n으로 나누었을 때 나머지가 y라면 그 해가 정답이다.

 

m씩 증가시키다가 마지막 해인 m과 n의 최소공배수를 넘으면 반복문을 종료한다.

 

만약 n으로 나누었을 때 나머지가 0이라면 정답인 해여도 찾지 못할 수 있다. 예를 들어 m=10, n=12, x=10, y=12라면 가장 마지막 해인 60을 찾아야 하지만 나머지가 0으로 계산되어 y인 12와 맞지 않아 정답인 해를 찾지 못한다. 나머지가 0일 때 12로 반환하기 위해 나머지를 계산하기전에 1을 빼주고 나머지를 계산 후 다시 1을 더해준다.

 

코드

#6064번 카잉 달력
import sys
input = sys.stdin.readline
from math import gcd
if __name__ == "__main__":
  t = int(input())
  for i in range(t) : 
    m,n,x,y = map(int,input().split())
    common_multiple = (m*n)//gcd(m,n)
    num = 0
    answer = -1
    while m*num+x <= common_multiple : 
      if (m*num+x-1)%n+1 == y : 
        answer = m*num+x
        break
      num += 1
    print(answer)