[BOJ][Python]6064번 풀이

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

6064번: 카잉 달력

t = int(input())
for _ in range(t):
    m,n,x,y = map(int, input().split())
    a,b = 0,0
    ans = 0
    for i in range(m+abs(m-n)):
        if (i*m+x-1)%n == y-1:
            ans = i*m+x
            break
    if ans == 0:
        print(-1)
    else:
        print(ans)

오늘은 열대야 때문에 잠을 계속 설치다가 그냥 새벽에 일어나서 해당 문제를 풀기 시작했는데요. 모든 경우에 해당하는 풀이도 안나오고 예외를 몇 개씩이나 둬도 도저히 안풀려서 그냥 다시 자고 일어나서 풀었습니다. 잠을 더 자서 뇌가 쌩쌩해진건지 아니면 고민하다가 이제서야 답이 떠올랐는지는 모르겠지만요.

 

문제의 접근은 일반적인 산수입니다. 초가 분이되고 분이 시가 되는 것과 얼핏 비슷해보이지만 다른 점은 조건에 맞다면 앞뒤 숫자가 동시에 증가하기 때문에 처음에 직관적이지 않다는 점일까요. 해당 문제는 1:1, 2:2, 3:3 ... 같은 식으로 둘 다 같이 상승하다가 앞 숫자가 m보다 크면 1로, 뒤 숫자가 n보다 크면 1로 바뀌는 문제입니다. 가령 m=2, n=3이라면 1:1, 2:2, 1:3, 2:1 이런식이죠. 아마 눈치 빠르신 분은 최소공배수가 되면 사이클이 완전히 다 돌겠구나 생각을 하셨을 것 같습니다. 실제로 좋은 접근일 것 같기도 합니다. 다만 해당 문제는 m과 n의 최대크기가 40000이기 때문에 39999, 40000으로 m,n이 주어진다면 시간 제한에 걸리겠죠. 그래서 저는 어차피 답은 m 또는 n의 배수에 x나 y를 더해서 만들 수 있는 수가 된다는 점에 착안했습니다(논리적으로 그럴 수 밖에 없긴 합니다만). 그래서 저는 그냥 m을 기준으로 잡고 반복문을 진행했습니다. 몫이 중요한 문제가 아니기 때문에 반복문으로 몫은 상승시켜가면서 대조를 하는 방식을 사용했습니다. 다만 이렇게 할 경우 n의 나머지를 구하는 방식이기 때문에 n과 y가 같은 값으로 주어진다면 답이 구해지지 않습니다(같다면 나머지가 0으로 나오기 때문). 따라서 나눠주는 과정에서 n+1의 나머지를 구하거나 나머지가 y-1인지를 확인하면 문제 없겠죠.