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

백준 6064 - 문제

백준 6064 - 입/출력

---

풀이

<1, 1> 부터 시작해 주어진 M, N에 관련된 조건에 맞게 두 자연수를 1씩 증가(이 때 k도 1씩 증가) 해야 한다.

증가한 두 자연수가 <M, N>이 되기 전에 <x, y>와 일치하면, 그때의 k를 출력하면 된다.

기본적인 로직은 아래와 같다.

단순히 (M, N, x, y)가 (39999, 40000, 39999, 40000) 으로 주어져도 LCM(39999, 40000) = 1,599,960,000 이기에 위의 방식대로 모든 수를 다 구하면 시간초과가 발생할 것이다.

 

난이도가 실버1로 낮은 편이고, 주어지는 수 또한 작은 수에 해당되기에 중국인의 나머지 정리를 사용하지 않고도 풀이할 수 있다. 

아래와 같은 풀이 과정을 통해 접근이 가능하다.

 

구하고자 하는 k는 <1, 1>이  <x, y>가 되기 위해 (x = y)가 아닌 이상 M, N의 배수에 따라 결정지을 수 있다.

즉 아래와 같은 식을 생각할 수 있다.

k = x + M*q1 = y + N*q2
   = x + M*q1 - y = N*q2
   = (X - y) % N  = 0 ,  ( X = x + M*q1 )

즉, ( X - y ) % N이 0을 성립시키는 X의 값이 k와 같다.

카잉 달력의 마지막 해는 k <= LCM(M, N)을 만족하기에, M과 N의 최소공배수 이내에서 위의 조건을 만족하는 k를 찾지 못했다면, <x, y>는 유효하지 않은 표현이기에 -1을 출력해 주어야 한다. 

---

소스코드

소스코드 보기

---

출처

6064번: 카잉 달력