[백준 알고리즘/Python] 6064 카잉 달력

문제

 

문제 이해

1~40000까지 다 구하려다가 시간초과가 났습니다. 다른 방법을 찾아보는데 x를 고정시키는 방법이 있었습니다.

 

x를 고정시키고 M값을 더하면 x는 그대로있고 y만 변하게 됩니다.

ex)

10 12 3 7 의 값이 주어졌을 때 처음 1 1에서 1씩 2를 올려 3 3을 만듭니다! x값은 일치가 되었죠.

다음부터는 10씩 올립니다. 그러면 3 17 -> 3 27이 되겠지요. 하지만 y는 13이 되면 1로 돌아갑니다. 

 

1 1

3 3

3 (13)1

3 11

3 (21)9

3 (19)7

(종료)

이런 방식으로 시간을 단축시킵니다.

 

코드

test_case = int(input())

def lcm(num1,num2):
    for i in range(max(num1,num2),0,-1):
        if((num1%i) == 0 and (num2%i)==0):
            return (num1*num2)//i
    return (num1*num2)

for _ in range(test_case):

    M, N, x, y = map(int,input().split())

    count_M = x
    count_N = x

    #들어온 x값을 고정하고
    # y는 x만큼 점프할 수 있다. y의 최대치가 넘어가면 나머지로 하면 된다.
    # x의 주기는 M의 값이다.

    for i in range(x,lcm(M,N)+1,M): # x를 고정하고 시작

        while(count_N > N): # y값을 빼본다.
            count_N = count_N - N

        if(count_N == y): # 정답과 같은지 확인
            print(i)
            break

        count_N += M # y에 x의 1사이클을 더해줌

    else:
        if(count_N == y): # 정답과 같은지 확인
            print(i)
        else:
            print(-1)

x부터 시작합니다.

lcm() 매서드는 M,N의 최소공배수를 구합니다. 최소공배수가 없다면 M*N값을 반환합니다.

그리고 M의 크기만큼 for문을 점프합니다.

 

먼처 x 값은 정답과 맞추었으니 y값을 확인해봐야 합니다. y의 한계치에 벋어났다면 한계치 안까지 줄여봅니다.

그 다음 정답과 같은지 확인합니다.

만약 정답과 같지 않다면 x의 사이클을 추가합니다.

 

최소 공배수까지 구해도 정답이 안나오면 -1을 출력합니다.