[파이썬] 백준 6064 카잉 달력 문제 풀이 (중국인의 나머지 정리)

문제

문제 출처

백준 6064번 - 카잉 달력

문제 설명

이 문제는 주어진 두 주기 $M$과 $N$에 대해, 어떤 해(year)가 주어진 값 $x$와 $y$를 동시에 만족하는지 찾는 문제다. $x$는 $M$으로 나눈 나머지이고, $y$는 $N$으로 나눈 나머지인 값을 의미한다.

주어진 값들을 통해, 두 조건을 동시에 만족하는 가장 작은 year를 구하는 것이 목표다.

입력은 테스트 케이스마다 $M$, $N$, $x$, $y$의 값을 받아서, 이를 만족하는 year를 출력해야 한다.

• $M$은 첫 번째 주기의 주기
• $N$은 두 번째 주기의 주기
• $x$는 $M$으로 나눈 나머지
• $y$는 $N$으로 나눈 나머지

출력은 주어진 두 조건을 동시에 만족하는 가장 작은 year를 구하는 것이다. 만약 해가 존재하지 않으면 -1을 출력해야 한다.

---

브루트포스 알고리즘

처음에는 이 문제를 브루트포스 방식으로 접근할 수 있다. 주어진 $M$과 $N$에 대해, 처음 주어진 $x$값에서부터 시작해서 $M$만큼 증가시키면서 $N$으로 나눈 나머지가 $y$와 일치하는지를 확인하는 방식이다. 이 방법은 간단하고 직관적이다.

예를 들어, 주어진 $x$에서부터 시작해 $M$씩 더하면서, 그 값이 $N$으로 나누었을 때 $y$와 맞는지 체크하는 방식이다. 이 방법은 맞는 해를 찾으면 바로 출력하고, 찾을 수 없으면 -1을 출력하게 된다.

코드 구현

import sys
input = sys.stdin.readline

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

    found = False
    year = x
    while year <= M * N:
        if (year - 1) % N + 1 == y:
            print(year)
            found = True
            break
        year += M

    if not found:
        print(-1)

시간 복잡도

이 방식은 단순하고 쉽게 구현할 수 있지만, 시간 복잡도가 높아질 수 있다. 최악의 경우 시간 복잡도는 $\mathcal{O}(M \times N)$으로, $M \times N$까지 반복할 수 있기 때문에, M, N이 커질 수록 매우 비효율적이다. 실제로 제출 후 채점 시간이 굉장히 오래걸렸다.

테스트 케이스가 많아질수록 상당한 시간이 소요되기 때문에 좀 더 효율적인 방법, 좀 더 빠르게 해결할 수 있는 방법은 없을까 계속 고민하던 중, 이 문제의 유형 분류에 처음 보는 유형이 있다는 사실을 알게 되었다.

---

중국인의 나머지 정리(CRT)

사실 처음 보는 유형이어서 무심코 넘겼는데 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)라는 이론이 존재하고, 이 방법을 사용하면 이 문제를 브루트포스 방식으로 접근하지 않아도 좀 더 효율적으로 풀 수 있다.

여기서 해결하고자 하는 문제는 두 개의 주기 $M$과 $N$에 대해 나머지가 각각 $x$와 $y$인 해를 구하는 문제로, 서로소인 두 모듈러 방정식이 있을 때 모든 모듈러 방정식을 만족하는 하나의 해를 구하는 CRT의 전형적인 문제 중 하나다.

중국인의 나머지 정리에서는 다음과 같은 두 조건을 동시에 만족하는 값을 구할 수 있다.

이 두 식을 동시에 만족하는 값을 구하기 위해서는 확장된 유클리드 알고리즘을 사용하여 모듈러 역원을 구하고, 이를 이용해 문제를 해결할 수 있다.

과정

1. 주어진 두 합동식:

   $\text{year} \equiv x \pmod{M}$
   $\text{year} \equiv y \pmod{N}$

2. 식 변환:
   첫 번째 식에서 $\text{year} = kM + x$라는 형태로 변환할 수 있다.
   이를 두 번째 합동식에 대입하면:

   $kM + x \equiv y \pmod{N}$

3. 식 정리:
   이를 $kM \equiv y - x \pmod{N}$로 바꿀 수 있다. 이때 $k$를 구하기 위해서는 모듈러 역원과 확장된 유클리드 알고리즘을 사용해야 한다.

   $M^{-1}$을 모듈러 역원이라고 하면 다음을 만족한다.

   $M \times M^{-1} \equiv 1 \pmod{N}$

   즉, $kM \equiv y - x \pmod{N}$의 양변에 $M^{-1}$을 곱하면 나눗셈을 대신할 수 있다.
   이를 통해 $k$의 최종 식을 구할 수 있다.

   $k \equiv (y - x) \times M^{-1} \pmod{N}$

4. 최종 계산:
   $k$를 구한 후 이를 원래 식에 대입하여 해를 구할 수 있다.

코드 구현

import sys
from math import gcd

def extended_gcd(a, b):
    """확장된 유클리드 알고리즘을 이용해 ax ≡ 1 (mod b)의 해 x를 찾음"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def solve(M, N, x, y):
    """중국인의 나머지 정리를 이용해 최소의 year 찾기"""
    # (x, y)에서 x와 y를 1-based index에서 0-based index로 변환
    x -= 1
    y -= 1

    # M * k ≡ (y - x) (mod N) 풀기
    g, m_inv, _ = extended_gcd(M, N)

    # 해가 존재하지 않는 경우
    if (y - x) % g != 0:
        return -1

    # k 계산 (M의 역원을 곱해서 (y - x) / g를 찾기)
    k = ((y - x) // g * m_inv) % (N // g)

    # year 계산
    year = M * k + x + 1  # 다시 1-based index로 변환

    return year

# 입력 처리
input = sys.stdin.readline
T = int(input())

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

시간 복잡도

중국인의 나머지 정리를 사용하여 문제를 해결할 경우, 확장된 유클리드 알고리즘을 실행하는 과정과 이를 통해 구한 모듈러 역원을 이용해 해를 구하는 과정이 필요하다.

확장된 유클리드 알고리즘을 실행하는 과정의 시간복잡도는 $\mathcal{O}(\log N)$이고, 해를 구하는 과정의 시간 복잡도는 $\mathcal{O}(\log N)$이다.

즉, 전체 시간 복잡도는 $\mathcal{O}(\log N)$이 된다.

이 방식은 M, N이 커져도 굉장히 효율적으로 빠르게 계산이 가능하다.

---

결론

이번 문제를 풀면서 두 가지 방식의 차이를 확실히 느낄 수 있었다. 브루트포스 방식은 코드가 간단하고 직관적이지만 실행 속도가 느린 반면, 중국인의 나머지 정리를 사용한 방식은 코드가 조금 더 복잡하지만, 훨씬 더 빠른 속도를 자랑했다. 두 방식의 특징을 비교해보면 다음과 같다

방식	코드 간결성	시간 복잡도	실행 시간	특징
브루트포스 방식	간단	O(n^2)	상대적으로 오래 걸림	직관적이고 구현이 쉬움
중국인의 나머지 정리	복잡	O(log n)	매우 빠름	효율적이고 최적화된 방법, 구현이 어려울 수 있음

정리

브루트포스 방식은 직관적이고 쉽게 구현할 수 있지만, 시간이 오래 걸린다. 반면, 중국인의 나머지 정리 방식은 성능 면에서 뛰어나지만 구현이 복잡하다. 이 문제를 통해 두 가지 방식의 장단점을 잘 파악할 수 있었고, 문제에 따라 적합한 방법을 선택하는 것이 중요함을 깨달았다.

결국, 어떤 방식이 더 좋은지는 문제의 성격에 따라 다를 수 있기 때문에 다양한 접근을 고려하는 것이 중요하다. 이번 문제는 그 점에서 정말 유익하고 재미있는 경험이었다.

---

기타 추가 설명

모듈러 역원

모듈러 연산은 어떤 수를 m으로 나눴을 때 그 나머지를 구하는 연산이다. 그리고 모듈러 역원은 다음 식을 만족하는 b를 찾는 것이다.

$a \times b \equiv 1 \pmod{m}$

즉, 어떤 수 a와 b를 곱했을 때 m으로 나눈 나머지가 1이 되는 b를 찾는 것이다. 이 때 b를 모듈러 역원이라고 한다.

모듈러 역원이 존재하려면, a와 m이 서로소여야 한다.

유클리드 알고리즘

유클리드 알고리즘은 두 수의 GCD(최대공약수)를 빠르게 구하는 방법이다.
기본적인 원리는 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 것이다. 이 원리를 이용하여 최대공약수를 빠르게 구할 수 있다.

def gcd(a, b):
    while b:  # b가 0이 아닐 때만 실행
        a, b = b, a % b  # a를 b로 바꾸고, b를 a % b로 변경
    return a

배주 항등식

배주 항등식은 두 정수 a와 b의 최대공약수 gcd(a, b)를 두 수의 선형 결합으로 나타낼 수 있다는 이론이다.

즉, a와 b가 주어졌을 때, $\gcd(a, b) = d$라면, 다음과 같은 형태로 d를 나타낼 수 있다.

$a \cdot x + b \cdot y = d$

이 때 d가 1이라면 x는 a의 모듈러 역원이다.

유클리드 알고리즘은 두 수의 최대공약수를 구하는 과정에서 그 나머지를 선형 결합으로 표현하는데, 이 선형 결합의 계수가 x, y이고, 배주 항등식의 해가 된다.