백준 6064번 카잉달력 파이썬

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

6064번: 카잉 달력

M,N이 주어지고 x,y가 주어진다. 현재 년에 대한 표시는 <x,y>로 한다. 

예시를 풀어보자면 현재 년을 M,N으로 나눈 나머지가 각각 x,y이다.

 

가장 처음한 생각은 그냥 브루트포스로 1부터 최대년까지 다 M,N으로 각각 나눈 나머지가 x,y일 때를 답으로 출력하는 것이었다. 하지만 이러한 방법으로 하니 M과 N의 최소공약수만큼이나 처리를 해야해서 시간초과에 걸렸다.

 

브루트포스를 사용하되 시간을 줄이려면 아예 의미 없는 케이스는 건너뛰는 형식으로 해야한다고 생각이 들었다. 구하고 싶은 값을 ans라 두면 ans = M* '어떤수1' + x 인걸 알 수 있다. ans는 정수이므로 어떤 수들도 정수이다. 그러므로 어떤 수를 1부터 증가하게 해서 M씩 건너뛰면서 처리를 한다면 시간을 M분의 1이나 줄일 수 있다.

 

ans = N* 어떤수2 +y 라고 그냥 ans를 N으로 나눈 나머지가 y일때 ans라 한다면, y가 N일때 문제가 생긴다.

ans=N*(어떤수2+1)이 되어버려서 나머지가 0인 것으로 나와 정답이 없는 것으로 처리가 된다. 그러므로 ans-y를 N으로 나눈 나머지가 0이라고 해서 풀었다.

 

이를 코드로 나타내면 

import sys
input=sys.stdin.readline

def GCD(x,y):#최대공약수 구하는 법
    while(y):
        x,y=y,x%y
    return x


T=int(input().rstrip())
for _ in range(T):
    M,N,x,y = map(int,(input().rstrip()).split())
    gcd=GCD(M,N)
    ans=-1
    while x<=M*N//gcd: #최대공약수까지 M씩 건너뛰면서 대입
        if (x-y)%N==0:
            ans=x
        x=x+M
    print(ans)

 

 

브루트포스 방법 외에는 중국인의 나머지 정리로 푸는 방법이 있다만 실버1 치고는 정수론이나 구현이 어려워 필자는 그렇게 풀지 않았다. 그 방법이 궁금하다면 아래 포스트를 참고하길 바란다.

https://choiseokwon.tistory.com/236