백준 6064번 : 카잉달력(python)

코드

def gcd(m,n):
    if(m>n):
        if(m%n!=0):
            return gcd(n,m%n)
        else:
            return n
    else:
        if(n%m!=0):
            return gcd(m,n%m)
        else:
            return m
def cal(m,n,x,y,c):
    a=x
    while (a<=c):
        if(a%n==y%n):
            return a
        a+=m
    return -1
num=int(input())
for i in range(num):
    m,n,x,y=map(int,input().split())
    max=gcd(m,n)
    c=m*n//max
    print(cal(m,n,x,y,c))

코드설명

m,n의 최소공배수까지 반복되다 최소공배수 다음숫자는 다시 원점으로 돌아가게된다.

유클리드 호세법으로 최소공배수를 구해줌으로 cal함수의 while문의 종료지점을 설정해준다.

x를 n으로 나눈것과 y를 n으로 나눈것이 같다면 카잉달력에 부합하는 값이 나오게된다.

느낀점 및 배운점

- 반복문의 가장 중요한 것은 종료지점 조건을 어떻게 설정해주냐인것같다.

- 처음에는 규칙으로 찾지 못해 헤메다, 직접 종이에 카잉달력을 써보면서 해결책을 얻었다. 머릿속으로만 생각하지말고, 직접 눈으로 봐가면서 푸는게 헷갈릴때는 더 좋은방법인거같다.

- 시간초과가 나면 그리 먼곳에 답이 있지않다. 반복문을 조금만 바꿔보자