[Python] 백준6064 카잉 달력

21 Jan 2023 in Study on Algorithm

백준6064 카잉 달력 링크

문제

예제 입력

---

코드

import sys

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

    while (x <= M * N): # lcm(m, n), 적어도 M * N 안에 결과가 있음 이후 값은 반복됨.
        if x % N == y % N: # <10, 12> => <3, 9>이면 X를 3으로 고정하고 한바퀴 마다 y값(%N은 12=0) 확인.
            print(x)
            break
        x += M
    else:
        print(-1)

설명

파이썬을 통해서 사용자로부터 입력받아 카잉 달력를 구현했습니다.

---

정리

# 최소공배수 (유클리드 호제법 이용)
def lcm(a, b):
    res = a*b
    if b > a:
        a, b = b, a

    while b != 0:
        a %= b
        a, b = b, a
    return res//a

그 외에도 유클리드 호제법 알고리즘으로 최소공배수를 구할 수 있지만 시간 초과가 발생합니다.

---

결과