[백준/파이썬] 6064번 카잉 달력 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 6064번 카잉 달력
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

두 주기 M, N과 목표 좌표 x, y가 주어질 때 해당 연도를 찾는 문제입니다. 없으면 -1을 출력합니다.

코드

import sys

def gcd(x, y):
    while y != 0:
        r = x % y
        x = y
        y = r    
    return x

def lcm(x, y):
    return x*y//gcd(x,y)

for i in range(int(sys.stdin.readline())):
    M, N, x, y = tuple(map(int, sys.stdin.readline().split()))

    end = lcm(M, N)
    
    if True if M > N else (False if M < N else x > y):
        years = [x + M*i for i in range((end-x)//M+1)]
    else:
        years = [y + N*i for i in range((end-y)//N+1)]

    flag = False
    for year in years:
        if (year%M, year%N) == (x%M, y%N):
            flag = True
            break
    print(year if flag else -1)

설명

최소공배수 범위까지만 후보 연도를 생성해 (year % M, year % N)이 목표와 일치하는 값을 찾습니다.

---

• 백준 문제풀이 전체 목록 보기

---