[구현/수학] 백준 6064 카잉 달력 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

6064번: 카잉 달력

 

 

 

2. 문제 풀이

 카잉 달력에서 <x:y>해는 몇 번째 해인지 구하는 문제입니다. 한 해가 지날 때마다 x와 y를 1씩 더하며 x는 M+1진법을, y는 N+1진법을 따릅니다. 

 

 M = 2, N = 3, x = 2, y = 1일 때
1) 1:1
2) 2:2
3) 1:3
4) 2:1

 위 예시는 4번째 해가 답이 됩니다.

 x와 y 모두 1씩 더해나가므로, Z번째 해는 <Z%M, Z%N>와 같습니다.. (<0, 0>부터 시작으로 가정)

 이 때 구해야할 답은 x = Z%M, y = Z%N일 때, Z입니다.  

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#최소공배수 (유클리드 호제법 이용)
def lcm(a, b):
    res = a*b
    if b > a:
        a, b = b, a

    while b != 0:
        a %= b
        a, b = b, a
    return res//a

T = int(input())
for _ in range(T):
    M, N, x, y = map(int, input().split())
    #마지막해인 M, N의 최소공배수까지 검사
    while (x <= lcm(M,N)):
        if x % N == y % N:
            print(x)
            break
        x += M
    else:
        print(-1)

 x = Z%M, y = Z%N일 때, Z를 구하기 위해서 x와 y를 1씩 증가시키면서 카운트를 세면 시간초과가 납니다.(브루트포스)

 애초에 while문을 제한할 최소공배수를 구하는 것 조차 시간초과가 뜹니다. 그 대신에 x 또는 y를 고정시키고, 고정시킨 변수의 진법 크기만큼 카운트를 올립니다. 

 

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    M, N, x, y = map(int, input().split())

    while (x <= M * N):
        if x % N == y % N:
            print(x)
            break
        x += M
    else:
        print(-1)

 아무래도 -1인 경우에 M, N의 크기가 작은 듯한데... 어쨌든 최소공배수보다 비효율적인 것 같지만... M*N의 곱으로 대신하면 통과가 됩니다.