[백준] 6064번 카잉 달력 ★

💡문제접근

• 구하고자 하는 연도를 1로 초기화한 다음 1씩 증가하여 조건을 만족시키는 값이 된다면 연도를 출력하고 아니라면 -1을 출력하는 방식으로 코드를 작성했지만 시간초과(TLE)가 발생했다. 그도 그럴것이 N, M의 최댓값은 40,000까지로 매우 큰 값으로 1씩 증가시키면서 비교하면 엄청난 시간이 소모될 것이다.
• 입력값을 기준으로 이해하기 쉽게 설명하자면 다음과 같다.
• year = M × p + x를 만족하면서 year = N × q + y를 만족시킨다. year값은 x 혹은 y로 초기화시키고 x or y만큼 증가시키면서 만족하는 경우를 찾으면 된다.

💡보충설명 표

• [테스트케이스 1] : 10 12 3 9

연도	x	y	연도 % 10	연도 % 12
9	3	9	9	9
21	3	9	1	9
33	3	9	3	9
45	3	9	5	9

• 연도의 초기값을 x 혹은 y로 설정한 다음 10과 12로 나눈 나머지가 각각 3과 9가 된다면 해당 연도를 출력, 하지만 연도가 M과 N의 최소공배수를 넘어선다면 -1을 출력한다.

💡코드(메모리 : 31256KB, 시간 : 3276ms)

import sys
input = sys.stdin.readline

T = int(input().strip())
for _ in range(T):
    M, N, x, y = map(int, input().strip().split())
    year = x
    flag = False
    while year <= M * N:
        if (year - x) % M == 0 and (year - y) % N == 0:
            flag = True
            break
        else:
            year += x

    if flag:
        print(year)
    else:
        print(-1)

💡소요시간 : 1h