카잉 달력 6064번 백준

문제:www.acmicpc.net/problem/6064

6064번: 카잉 달력

이 문제는 시간초과를 해결하지 못한 문제이다. 

 

import sys
def gcd(left,right):
    if right==0:
        return left
    return gcd(right,left%right)
 
 
testCase = int(sys.stdin.readline())
for _ in range(testCase):
    N,M,fx,fy=map(int,sys.stdin.readline().rstrip().split())
    x,y=1,1
    count=1
    if M>N:
        big=M
        small=N
    else:
        big=N
        small=M
    total=(big*small)/gcd(big,small)
    while True:
        if count>total:
            print(-1)
            break
        if fx==x and fy==y:
            print(count)
            break
 
        if count==1:
            x=fx
            if(1+fx-x)%M!=0:
                y=(1+fx-1)%M  
            else: y=M
            count=fx
        else:
            if (y+N)%M!=0:
                y=(y+N)%M
            else: y=M
            count+=N

 

 

처음에 이 문제를 접근했을 때에는 날짜 계산으로 접근하다가 아무래도 시간에 대한 제한에 걸릴 것 같아서 N,M의 최소공배수를 구한 다음에 그 숫자 이전까지 내가 찾고자 하는 값이 있는지 확인하는 식으로 코드를 짰다. 근데 아무래도 최소공배수 구하는 과정이 시간초과로 가지 않았나 싶다. 

그래서 구글에 검색하여 정답코드를 봤다.

 

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))

참고: https://pacific-ocean.tistory.com/126

[백준] 6064번(python 파이썬)

내가 찾고자 하는 값이 K라 하자.  K에 X를 빼고 M을 나눈 나머지가 0 또는 K에 Y를 빼고 N을 나눈 나머지가 0이었을 때유효한 표현이다. 그렇다면 X에서 K까지 더한 다음 Y를 빼고 그 값에 N을 나눌 때 나머지가 0이 된다면 참이 된다는 소리이다. 단 X에서 K까지 더할 때에는 +M식 해야 한다. 왜냐하면 (K-X)%M=0라는 식이 성립하기 때문이다.

 

그러면 위와 같은 식이 완성된다.