6064 카잉 달력 파이썬

문제 )

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

6064번: 카잉 달력

 

쉽다고 생각했는데 한참을 애먹은 문제...

시간제한은 1초인데 m, n은 4만까지 있고 그거마저도 test_case가 여러개가 있어서 브루트포스로 하면

1초만에 못한다고 생각을 했는데 가능하더라....ㅋ;;

 

내 힘으로 풀지 못해 다른 사이트의 코드를 참고했다.

 

소스코드 ) 

for _ in range(int(input())):
    m, n, x, y = map(int, input().split())
    ans = 1
    while x <= m*n:
        if x%n == y%n:
            print(x)
            ans = 0
            break
        x += m
    if ans:
        print(-1)

못 만들어지는 건 또 -1을 출력해야해서 만들수있는것과 못 만드는 것을 추리기 위해 브루트포스로 접근을 해야했나

라는 생각도 들었다. 처음 코드를 짤 때 -1을 출력을 못해서 막혔기 때문이다.

각설하고, 코드의 핵심 아이디어는 x를 고정을 하고 x에 m만큼을 계속 증가를 시켜준다 

그리고 y%n과 같아지는 순간이 우리가 구하는 x, y일때의 해를 구할 수 있다.

왜 그냥 y는 안되냐면 딱 맞게 떨어지는 경우가 있기 때문에 안된다.

n이 12인데 y가 12인 경우

 

아, 그리고 이 문제를 풀며 알았는데 m과 n이 10과 12일때 나올 수 있는 해의 총 경우의 수는 60이다.

10과 12의 최소공배수만큼이다.