[BOJ] 6064 : 카잉 달력 [정수론](Python)

문제 링크

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

6064번: 카잉 달력

소스 코드

def num(m, n, x, y):
    while x <= m * n: # 최대 범위
        if (x-y) % n == 0: # 나머지로 확인
            return x
        x += m
    return -1

t = int(input())
for i in range(t):
    m, n, x, y = map(int, input().split())
    print(num(m, n, x, y))

 

해설

• 시간 초과에 주의
• 나머지가 0인 경우 찾기

확실히 정수론이나 수학 관련 알고리즘 문제들은 DP와 마찬가지로 코드 구현 자체는 간단하지만 이 방식을 생각해내는 것이 굉장히 어려운 것 같다.

이 문제도 주먹구구식으로 풀이하는 코드를 작성했다가 시간 초과를 면치 못하고 다른 분들의 좋은 풀이를 찾아보았다.

시간 초과에 굉장히 엄격한 문제여서 한참 걸렸다.

 

나머지가 0인 경우 찾기

이 문제의 포인트는 나머지가 0인 경우를 찾아야 된다는 것에 있다.

예를 들어 k번째 해를 구하기 위한 방식을 구체화 해보겠다.

 

문제의 예시와 마찬가지로 k = 33 인 경우, m,n,x,y는 각각 10,12,3,9 로 주어져 있다.

이때 33이라는 숫자에 x를 빼고 m으로 나누거나, y를 빼고 n을 나눈 나머지가 전부 0이다.

 

(33-3) % 10 = 0, (33-9) % 12 = 0

 

거꾸로 생각하면 x, y(3, 9)에 각각 m, n을 적절히 더한 것이 k가 된다. 여기서 적절하다는 표현은 무엇으로 나누어도 나머지가 0이 되어야 한다는 뜻이다. 일종의 최소공배수로 이해할 수 있겠다.

 

while문의 범위

소스 코드로 돌아가보자. while문의 범위는 m,n 둘을 곱한 값으로 설정되어 있다. 이는 둘을 곱한 값까지 해를 셀 수 있고 그 다음을 넘어서는 셀 수 없기 때문이다.

 

조건문을 이해하는 것은 엄청 직관적이지는 않다.

위에서 설명한 목표인 k가 곧 x라고 생각하면 조금 낫다. 

x에 계속 m을 더하면서 k가 될 때까지 과정을 반복하는 것이다.

 

x+m 이 된 값에서 y를 빼고 이것이 n으로 나눠 떨어지는지 확인한다.

구체적인 숫자를 적용하면 x = 3 에 m = 10을 더하면 13이고, 이를 y로 빼면 13-9 = 4가 된다.

이는 n = 12으로 나눠 떨어지지 않으므로 무시하고 또 m을 더한다.

그러면 x = 13 + 10 = 23 이 되고 여기에 y를 뺀 값 23 - 9 = 14 는 n=12로 나눠 떨어지지 않는다.

마지막으로 x = 23 + 10 = 33 이 되고, 여기에 y를 뺀 값 33 - 9 = 24는 n=12로 나눠 떨어진다.

 

따라서 x가 우리가 원하는 k가 된 것으로 이해하고 x를 바로 반환하면 된다.

 

반복문이 끝날 때까지 해당 조건을 만족하지 못하는 경우는 구할 수 없는 해를 구하라고 한 것이므로 -1을 반환한다.