[백준/Python] #6064번 카잉 달력

문제 

• x, y가 각각 M, N보다 작다면 전날 + 1, 작지 않으면 1
• <M:N>은 달력의 마지막 해이고, <x:y>가 몇 번째 해인지 구하는 문제 

M, N  <10, 12>	1일	2일	3일	4일	5일	6일	7일	8일	9일	10일	11일
x	1	2	3	4	5	6	7	8	9	10	1
y	1	2	3	4	5	6	7	8	9	10	11

→ 10일을 보면 x는 M과 같은 값으로 M보다 작아야 한다는 조건을 만족하지 못하므로 11일에 1로 초기화 해준다.

 

입력

1. 테스트 데이터의 개수 T
2. T개의 M, N, x, y (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 

3
10 12 3 9
10 12 7 2
13 11 5 6

 

출력

<x, y>가 몇 번째 해인지(유효하지 않으면 -1 출력)

33
-1
83

 

 

정답

import sys
input = sys.stdin.readline

def cal_year(M, N, x, y):
    tmp = x
    while tmp <= M * N: # tmp의 범위는 M*N을 넘을 수 없다.
        if (tmp - x) % M == 0 and (tmp - y) % N == 0:
            return tmp
        tmp += M
    return -1

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        M, N, x, y = map(int, input().split())
        print(cal_year(M, N, x, y))

 

해결 아이디어

• 처음에는 <M, N>까지의 일 수를 계산하고, 해당 일 수 안에 입력받은 <x, y>가 존재한다면 존재한 날짜를 반환하고 존재하지 않는다면 -1을 반환하도록 했지만 시간 초과가 발생했다.
• 알고 보니 이 문제를 풀기 위해서는 특정 공식이 필수였던 것,,
• 위의 코드는 일정한 주기를 가진 두 주기의 일치 시점을 계산해 주는데 특정한 시점에서 시작된 두 주기 <M, N>에 대해 그 값이 일치하는 가장 작은 시점을 찾아준다. 
• 주기의 곱인 M * N까지 반복하며 `(tmp - x) % M == 0`, `(tmp - y) % N == 0`로 현재 시점을 나타내는 tmp가 해당 주기를 따르고 시작 값에 맞춰지는지를 확인한다. 이 조건들이 만족한다면 tmp를 반환, 만족하지 않으면 -1을 반환한다.