[백준 - Python] 6064. 카잉 달력 (완전 탐색)

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

코드

import sys
input = sys.stdin.readline

T = int(input())

def num(M, N, x, y):
    k = x
    while k <= M * N:
        if (k - y) % N == 0:
            return k
        k += M
    return -1


for _ in range(T):
    M, N, x, y = map(int, input().split())
    print(num(M, N, x, y))

 

k를 1씩 늘리면서 완전 탐색을 진행하면 시간초과가 발생한다.

따라서 이 방법 이외로 k값을 찾을 수 있는 간편한 식을 구하는게 문제 풀이의 관건이었다.

 

k, 즉 <x, y>가 몇 번째 해인지를 알려주는 숫자는

(k-x) % m = 0 혹은

(k-y) % n = 0을 만족시키는 어떤 수이다.

 

즉, (k-x)가 m의 배수인 수를 찾거나, (k-y)가 n의 배수인 수를 찾고

나머지 식도 만족하는지 확인하면 된다.

 

k를 x 혹은 y 하나로 초기화 해두고

M 혹은 N을 더해주면서 배수 단위로 늘려주고,

나머지 식을 만족하는 지 확인하여

두 식 모두 만족하는 K를 구했다.

 

 

참고 자료

https://velog.io/@dhelee/%EB%B0%B1%EC%A4%80-6064%EB%B2%88-%EC%B9%B4%EC%9E%89%EB%8B%AC%EB%A0%A5-Python-%EB%B8%8C%EB%A3%A8%ED%8A%B8-%ED%8F%AC%EC%8A%A4