BOJ #6064 카잉 달력

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 6064. 카잉 달력

문제 풀이 - 1(시간초과)

문제를 보니 주어진 기준값 M, N을 기점으로 초기화된다는 점에서 합동식을 떠올릴 수 있다. 즉 2개의 연립 합동식을 푸는 문제로 해석할 수 있으니 최소공배수를 구해서 계수를 정리한 뒤 카잉 달력 표기법으로 바꿔서 동일한 지 체크하면 된다.

python 코드

import sys
 
def LCD(M, N):
    i, j = M, N
    while j != 0:
        r = i % j
        i = j
        j = r
    L = (M * N) // i
    return L, L // M, L // N
 
def check(k, M, N, x, y):
    i, j = k % M, k % N
    if i == 0:
        i = M
    if j == 0:
        j = N
    if x != i or y != j:
        return False
    return True
 
T = int(input())
for _ in range(T):
    M, N, x, y = map(int, sys.stdin.readline().split())
    p, a, b = LCD(M, N)
    q = a - b
    k = x * a - y * b
    while k % q != 0:
        k += p
    k //= q
    if k < 0:
        k += p
    if check(k, M, N, x, y):
        print(k)
    else:
        print(-1)

그러나 이 해결법은 시간초과(TLE)가 발생한다. 아마도 최소공배수를 각각에 대해 구하는 과정에서 TLE가 발생하지 않았나 싶다. 그렇다면 시간 복잡도를 더 줄여야 한다. 검토 가능한 범위의 최대값은 M * N이니 해당 범위에서 어떻게 줄여나갈 지 고민해야 한다.

문제 풀이 - 2

최소공배수를 구하고 또 합동식을 해결하느라 while문 2개가 들어가버리는 바람에 시간초과가 된 듯 싶다. 그렇다면 최대 범위를 상정해 두고 최대한 간격을 띄우면서 탐색을 진행하여 조건에 맞는 값이면 그대로 중지하고 값을 반환하는 1차원적 풀이를 생각해야 한다.

python 코드

import sys
 
T = int(input())
for _ in range(T):
    M, N, x, y = map(int, sys.stdin.readline().split())
    k = x # 기준값
    sol = -1 # 값이 없으면 -1
    if x == M: # 합동식 0으로 치환
        x = 0
    if y == N:
        y = 0
    while k <= M * N: # 최대범위까지
        if k % N == y: # 만약 k가 N에 대해서도 y를 만족 시
            sol = k # 값 발견
            break # 탐색 중지
        k += M # 아니면 M을 더함 (k mod M 유지)
    print(sol) # sol 출력

좀 더 M, N 값에 대해 x, y의 조건을 건다던지 제약을 둬서 시간을 절반까지 줄일 수 있어 보인다. (예를 들면 M, N이 모두 짝수일 때, x + y가 홀수라면 무조건 -1) 시간복잡도는 O(n)이다.