[Python] 백준 6064_카잉달력 (최소공배수 활용)

문제 설명

---

문제 이해

M = 10, N = 12 인 경우, 년도가 어떻게 표현되는지 확인해보면

<1 : 1> : 1번째 해

<2 : 2> : 2번째 해

<3 : 3> : 3번째 해 ...

<10 : 10> : 10번째 해 이고, x(10) >= M(10) 이기 때문에 다음 11번째 해는 <1 : 11> 가 된다.

<2 : 12> : 12번째 해 이고, y(12) >= N(12) 이기 때문에 다음 13 번째 해는 <3 : 1> 이 된다.

<4 : 2> : 14번째 해 .. 이렇게 연도가 증가하는 방식이 카잉 달력이라고 한다.

 

M = 10, N = 12일 때, <3:9>가 몇번째 해인지 알아보는 방법은 

x가 3인 경우를 살펴보면 3번째일 때, 13, 23, 33, 43, 53번째 해일 때이다.

x가 M(=10)씩 증가할 때마다 x로 표현된다는 것을 알 수 있다. y도 마찬가지이다.

 

따라서 33번째 해를 최댓값(M, N)으로 나눈 나머지를 구하면 <x, y>로 표현할 수 있다.

33번째는 M이 3번 반복되고 3해가 더 지나면 33번째 이므로 x = 3이다. (= 33 % M)

또, N이 2번 반복되고 9해가 더 지나면 33번째 이므로 y = 9이다. (= 22 % N)
따라서 33번째 해는 <3:9>로 표현되는 것이다.

 

이처럼 3번째 해인 <3:3> 은 <3 % 10 : 3 % 12>

13번째 해인 <3:1>은 <13 % 10 : 1 % 12> 와 같다. 

 

그럼 종말하는 마지막 해는 어떻게 구할까?

<x:y> 가 <m:n>이 되는 순간이 종말하는 해인데, x는 m 만큼, y는 n 만큼 증가하기 때문에 <x:y>가 m과 n으로 나누어지는 최소값이 마지막 해가 된다는 것을 알 수 있다. 그러니까 최소공배수가 마지막번째 해 라는 것을 알 수 있다.

 

💡 그럼, 3, 13, 23, 33, 43, 53번째 해일 때 y의 값을 계산해보면 되지 않을까?

👉 기준을 x 로 잡고 x로 표현할 수 있는 해를 구한 뒤, 해당 해를 y 로 표현하고 y의 값과 일치하는지를 확인하면 된다.

몇번째 해인지를 answer 변수에 담아서 x로 표현할 수 있는 가장 작은 년도인 x부터 M 씩 증가시킨다.

그다음 answer를 y로 표현하면 어떤 값인지 구한다.

answer 번째 해일때, <x:y>로 표현하면 x >= M 일 때, y >= N 일 때 다시 1로 순환 된다.

👉 위의 표 처럼 입력받은 x로 표현 되는 해인 answer 값을 구한 뒤, answer를 y로 표현 했을 때의 값과 입력받은 y의 값을 비교하면 된다.
일치하는 경우, 몇번째 해인지 찾은 것이므로 answer를 출력한다.

answer의 값이 마지막 해인 m과 n의 최소공배수보다 클 때까지 <x:y> 와 일치하는 해를 찾지 못하면 유효하지 않은 표현이므로 -1을 출력한다.

따라서 33번째 해일 때, <3 : 9> 로 표현될 수 있다.

 

🤯 이때 문제가 있다!

마지막 해인 <10:12> 를 입력받은 경우 <answer % M : answer % N> = <0:0>이다.

이를 보정하기 위한 식이 필요하다.

y가 N 과 동일하면 answer % N은 0 이 되므로 y는 [0 ~ N - 1] 범위로만 표현할 수 있다.
answer를 y로 표현한 값을 구할 때, (answer - 1) % n을 구하고 +1 을 해주면 [1 ~ N] 범위로 구할 수 있다.

조건식 : if (answer - 1) % n + 1 == y

마지막 해

소스 구현

• 우선, 멸망 해인 최소 공배수를 구하기 위한 함수를 작성했다.
• m, n, x, y를 입력 받는다.
• answer 변수를 x의 값으로 초기화시킨 뒤 값을 M씩 증가시키면 answer의 값은 x로 표현할 수 있는 해이다.
  그럼 answer의 값이 y로 나타낼 수 있는지를 확인하면 된다.
• ‼️ 만약 구한 값이 n으로 안나눠지거나, 멸망해보다 큰 경우 <x:y>로 표현할 수 없는 해이기 때문에 -1을 출력한다.

import sys

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def lcm(a, b):
    return m * n / gcd(a, b)

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    m, n, x, y = map(int, sys.stdin.readline().rstrip().split())
    max_year = lcm(m , n)
    answer = x
    while answer <= max_year: # 멸망해
        if (answer - 1) % n + 1 == y:
            break
        answer += m     # x의 최대값인 m 만큼 증가
    if answer > max_year:
        print(-1)
    else:
        print(answer)

 

---

실버1 난이도의 문제인데 사실 너무 어려웠던 문제다. 멸망 해가 최소 공배수인건 알겠는데, <x:y>가 몇번째 해인지 구할 방법을 도저히 못찾았다. 풀이를 보고도 이해가 안돼서 손으로 하나하나 천천히 따라가다가 겨우 풀었다. 🫠

이런 문제는 블로그에 설명하면서 정리해봐야 완전히 내 걸로 만들 수 있기 때문에 시간을 들여 열심히 작성했다.

 

 

문제가 있는 경우 댓글로 알려주시길 바랍니다.

감사합니다.