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

문제 정리

if x < M x' = x + 1, else x' = 1
if y < N y' = y + 1, else y' = 1

1476번 실버5 날짜 계산이랑 비슷한 문제이다. 하지만 조건이 더 까다로웠다.

• 시간 제한
• 날짜 범위
• 예외 케이스

풀이

1. 첫 풀이

   t = int(input()) # 테스트 케이스의 수
   for _ in range(t):
       m, n, x, y = map(int,input().split()) 
       tx, ty = 0, 0
       year = 0
       for i in range(1,m*n+1):
           tx += 1
           ty += 1
           year += 1
           if tx == x and ty == y:
               break
           if tx == m:
               tx = 0
           if ty == n:
               ty = 0
       if year == 1: # 예외 케이스 추가
         year = 1  
       elif year == n*m: # 처음부터 끝까지 탐색함에도 해가 없을 경우
           year = -1
       print(year)

   첫 풀이는 답은 나오나 시간제한에서 막혔다. 아무래도 모든 조건을 다 탐색하는 방식이라 O(m*n)의 시간이 걸려 안됐던거 같다.
   여기서 규칙을 찾거나 공식을 만들어야 함을 깨달았다.

2. 두 번째 풀이
   모듈러 연산을 활용하는 것이 핵심이다.
   M, N, X, Y를 관찰해보자.
   예를 들면, M = 10, N = 12인 경우, M의 주기는 10, 20, 30, ...이고, N의 주기는 12, 24, 36, ...이다.

   연도 X를 M으로 나눈 나머지와 N으로 나눈 나머지가 주어진 값과 일치하는 지점을 찾아야 하는 것이다.
   예를 들면, M = 10, N = 12, x = 3, y = 9인 경우,
   연도 X는 X % 10 == 3과 X % 12 == 9를 만족하는 해가 있는가를 찾아내는 것이 핵심이다.

   한 주기의 모든 값에 대해 다른 주기의 값을 순차적으로 증가시키면서 조건을 만족하는 지점을 찾아야 한다.
   예를 들면, M = 10에 대해 X를 1부터 10까지 증가시키면서, 각각에 대해 N = 12의 주기를 순차적으로 확인하면 된다.

   종료조건은 M,N의 최소공배수을 넘어서는 것이다.

   def kaing(m,n,x,y):
   	# 예외 케이스 처리. 답이 1인 것
   	x -= 1 
       y -= 1
       # 이제부터 x는 년도로서 사용된다.
       while x < m*n: # 최소 공배수와 같거나 무조건 큰 값
       	if x%n == y: # 만약 M주기를 기준으로 나머지가 일치한다면?
   			return x+1 # x를 반환하면 된다. +1 의 의미는 예외처리를 위해 뺏던 값을 다시 더해주는 과정이다. 
           x+=m # 그러지 않다면 다음주기로 넘어간다.
   	return -1 # 모든 주기를 방문했음에도 연도를 못찾는다면 -1
       
   t = int(input())
   for _ in range(t):
   	m, n, x, y = map(int,input().split())
       year = kaing(m,n,x,y)
       print(year)

   즉, 연도 X를 M으로 나눈 나머지와 N으로 나눈 나머지가 주어진 값과 일치하는 지점을 찾는 것! 그것이 핵심이다.

더 좋을 풀이가 있을지도 모르겠다. 최소공배수를 구한다던가 말이다.. 하지만 나름 깔끔하게 잘 푼 거 같다.