[백준] 6064 : 카잉달력 in python 파이썬 코드, 반례

BAEKJOON 알고리즘 6064번 카잉달력 파이썬 코드

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

---

코드

for _ in range(int(input())):
    M, N, x, y = map(int, input().split());
    v = x
    while (v - y) % N != 0 and v <= M * N:
        v += M
    print(-(v > M * N) or v)

---

코드설명

이 문제는 반례가 많은 문제이다.

처음에는 다음과 같이 M의 배수 중에서 만족하는 것만 찾았다.

for _ in range(int(input())):
    M,N,x,y=map(int,input().split());i=1
    while ((M*i+x)-y)%N!=0 and M*i<=M*N:i+=1
    if x==y:print(x) 
    else:print(-(M*i>M*N) or M*i+x)

그랬더니 N이 더 작을 때 생기는 반례들이 있었다.

예를들면 8 2 4 2 일 때 답은 4이지만, 위 코드는 12를 밷는다.

다음으로 M의 배수와 N의 배수 중에서 만족하는 것을 찾고 둘 중 더 작은 값으로 출력했다.

for _ in range(int(input())):
    M,N,x,y=map(int,input().split());i=1;j=1
    while ((M*i+x)-y)%N!=0 and M*i<=M*N:i+=1
    while ((N*j+y)-x)%M!=0 and N*j<=M*N:j+=1
    if x==y:print(x)
    else:print(-(M*i>M*N) or min(M*i+x,N*j+y))

그랬더니 이번에는 시간초과가 떴다.

방법을 아예 바꾸어, x에 만족하는 가장 처음 숫자를 찾고, 거기에 M씩 더해가며 y도 만족하는지 찾았다.

while문을 두 번 쓴 것보다 하나를 고정시키니 더 효율적이다.

---

참고로 이 문제는 반례를 묻는 질문이 많아 누군가 정리해놓았다.

>> 40000 39999 39999 39998

1599959999

>> 40000 39999 40000 39999

1599960000

>> 40000 40000 40000 39999

-1

>> 40000 39998 40000 39997

-1

>> 39999 2 39998 2

39998

>> 3 40000 3 39999

39999

>> 40000 3 40000 3

120000

>> 8 2 4 2

4

>> 10 12 2 12

12

>> 12 10 12 10

60

>> 12 10 1 1

1

>> 12 6 12 6

12

>> 10 1 5 1

5

>> 1 10 1 5

5

>> 1 1 1 1

1

출처 : https://www.acmicpc.net/board/view/21503