코딩테스트 연습/백준

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

슈퍼짱짱 2019. 9. 8. 08:00
반응형

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



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




코드


1
2
3
4
5
6
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)
cs




코드설명


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

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


1
2
3
4
5
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)
cs


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

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


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


1
2
3
4
5
6
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))
cs


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


방법을 아예 바꾸어, 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

반응형