백준 6064번 파이썬 문제풀이(브루트 포스 - 카잉 달력) - 쉽게설명

 

사실 이문제는 다른 방식으로 아주 쉽게 풀 수 있지만 문제에서 요구하는 식을 찾지 못할 경우 계속해서 시간초과가 발생한다. 다른 블로그들도 찾아보며 코드를 봤지만 이해가 되지 않아 혼자 다시 풀어보며 최대한 이해하기 쉬운 식을 발견했다. 그 코드는 다음과 같다.

 

코드

import sys


def calculate(m, n, x, y):
    k = x #k를 x로 초기화
    while k <= m * n: #k의 범위는 m*n을 넘을 수 없기에
        if (k - x) % m == 0 and (k - y) % n == 0: #2개의 조건을 만족하는 k값을 찾는다.
            return k
        k += m #k-x가 m의 배수이기 때문에 k는 x로 초기화해주었기 때문에 m만 더해준다.
    return -1


t = int(input())

for _ in range(t):
    m, n, x, y = map(int, sys.stdin.readline().split())

    print(calculate(m, n, x, y))

-> 이 문제의 가장 중요한 점은 k 값을 찾기 위해 0부터 +1 씩 계산하는 코드가 나온다면 무조건 시간초과가 발생한다. 그렇다면 결국 k값을 찾을 수 있는 간편한 식을 찾아야 한다는 말인데 간단히 설명하겠다.

 

우선 이문제에서 첫번째로 찾아야 할 식이 바로 (k-x)%m = 0 이면서 (k-y)%n =0 이다. 사실 이식을 찾았으면 거의 문제는 다 푼것이다. 단, 여기서 k를 찾기 위해 k값을  0부터 x*y 까지 +1씩 증가시키며 돌면 시간초과가 발생한다. 따라서 한번더 k값을 어떻게 증가시킬껀지 생각을 해야한다.

 

잘생각해보면 (k-x)는 m의 배수 이고 (k-y)은 n의 배수이다.그래야만 나머지가 0이 나온다.  즉, x,y 둘중 하나만 이용해서 문제를 풀 수 있다는 것이다. (k-x) 가 m의 배수인 수를 찾거나 혹은 (k-y)가 n의 배수인 수 둘 중 만족하는 하나의 값만 찾아도 된다는 것이다.  그렇다면  (k-x)를 이용해보자. (k-x) % m = 0 을 만족시킬려면 k = x 이거나 k는 x+m 혹은 k는 x+2m..... 이런식으로 값을 가지게 된다. <- (이부분이 이해가 되면 이문제는 해결된 것이다. )

 

정리하면 k를 x로 초기화 한 후 추가적으로 m만 더해주면 된다는 것이다. 그렇게 m*n까지 돌았는데도 답이 안나온다면 x,y를 만족하는 k가 없다는 뜻이므로 -1을 출력한다. 이러한 설명을 이해한 뒤에 위의 코드를 보자.