[백준] 6064 카잉 달력 (python 파이썬)

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

6064번: 카잉 달력

 

덤

---

아이디어

1. 시간 초과

• 처음에는 x, y값이 나올 때까지 1씩 더해가며 count를 했다. 숫자가 반복되면 -1을 출력하게 했다.
• 생각이 너무 쉬웠는지 시간 초과가 발생했다.
• 다른 방법을 사용하기로 결정

---

코드 설명

def find_K(M, N, x, y):
    K = x

    while K <= M * N:
        if (K - x) % M == 0 and (K - y) % N == 0:
            return K
        K += M
    return -1

 

백준에 있는 첫 번째 예제 케이스 10 12 3 9로 예를 들어 설명하겠다.

우리가 구할 숫자를 K라고 하자.

그럼 그 K라는 숫자는 K = 10 * p + 3 = 12 * q + 9를 만족한다. (여기서 p, q는 자연수)

식을 변형해서 보면 (K - 3)은 10으로 나누어 떨어지고, (K - 9)은 12로 나누어 떨어진다.

이를 문자로 바꿔서 써보면 (K - x)는 M으로 나누어 떨어지고, (K - y)는 N으로 나누어 떨어진다.

 

이걸 코드에 적용하면 된다. 

K값은 M * N을 넘지 않으므로 K값을 증가시키면서 위 조건을 만족하는지 확인하면 된다.

근데 여기서 그냥 K를 1씩 증가시키면 또 시간 초과가 난다. 

 

K값을 다시 생각해보면 결국 K값은 M * p + x 또는 N * q + y이므로 

K의 초기값을 x로 선언하고 K값을 M만큼 증가시키면서 확인해보면 된다.

x대신 y, M 대신 N을 사용해도 됨.

---

전체 코드

import sys
T = int(input())

def find_K(M, N, x, y):
    K = x

    while K <= M * N:
        if (K - x) % M == 0 and (K - y) % N == 0:
            return K
        K += M
    return -1

for _ in range(T):
    M, N, x, y = map(int, sys.stdin.readline().rstrip().split())
    print(find_K(M, N, x, y))