[BOJ] 1476 - 날짜 계산

문제

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

준규가 사는 나라에서는 숫자 E, S, M 3개를 이용해서 연도를 나타낸다.  그리고 이 세 수는 아래와 같은 범위를 가진다.

• 1 ≤ E ≤ 15
• 1 ≤ S ≤ 28
• 1 ≤ M ≤ 19

우리가 알고있는 1년은 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다.

E S M 년도를 입력받아, 우리가 알고 있는 연도를 계산하라.

 

풀이

내 풀이

나는 연도를 증가시킨 후, 그 연도를 E S M 연도와 비교하는 방식을 사용했다. 순서는 다음과 같다.

 

1. E S M을 입력받는다.

2. E S M의 각 진수를 15, 28, 19로 취급할 수 있도록 입력값을 1씩 뺀다.

3. 연도를 증가시킨다. 반복을 줄이기 위해 E S M의 최대 진수인 28을 증가폭으로 한다.

4. E S 각각 진수에 대한 연도의 나머지를 계산하고, 그 값이 E와 S에 1을 뺀 값과 같으면 출력한다. 출력할 때에는 계산한 연도에서 1을 증가시켜야 한다.

 

코드

import sys

e, s, m = map(int, sys.stdin.readline().split())
e -= 1
s -= 1
m -= 1
i = 0
while True:
    y = 28 * i + s
    if y % 15 == e and y % 19 == m:
        print(y + 1)
        exit()
    i += 1

 

중국인의 나머지 정리 활용

이 문제는 15로 나눴을 때의 나머지가 E이고, 28로 나눴을 때의의 나머지가 S이고, 19로 나눴을 때의 나머지가 M인 수를 찾는 문제이다. 수식으로 표현하면 아래와 같다.

$$ x \equiv \mathrm{E} \pmod{15}$$

$$ x \equiv \mathrm{S} \pmod{28}$$

$$ x \equiv \mathrm{M} \pmod{19}$$

 

중국인의 나머지 정리는 아래와 같이 정리할 수 있다.

\( m_1, \cdots m_n\)이 \( \begin{matrix} gcd(m_i,m_j) = 1, & for i \ne j \end{matrix} \) 를 만족할 때, 일차연립합등식

$$ x \equiv a_1 \pmod{m_1}$$

$$ x \equiv a_2 \pmod{m_2}$$

$$ \vdots $$

$$ x \equiv a_i \pmod{m_i}$$

의 해는 아래와 같다.

\( M=m_1 m_2 \cdots m_n \)이고, \( M_i=M / m_i \)라고 할 때, 

$$ x \equiv \sum_{i=1}^N M_i(M_i^{-1} \mod m_i) a_i \pmod{M} $$

 

문제에 대입하여 계산해보자.

$$ M = m_1m_2m_3 = 15 \times 28 \times 19 = 7980 $$

$$ M_1 = M / m1 = 7980 / 15 = 532 $$

$$ M_2 = M / m2 = 7980 / 28 = 285 $$

$$ M_3 = M / m3 = 7980 / 19 = 420 $$

$$ \begin{matrix} x &\equiv& \sum_{i=1}^N M_i(M_i^{-1} \mod m_i) a_i \pmod{M} \\ &\equiv& (M_1(M_1^{-1} \mod m_1) a_1 + M_2(M_2^{-1} \mod m_2) a_2 + M_3(M_3^{-1} \mod m_3) a_3) \pmod{M} \\ &\equiv& (532(532^{-1} \mod 15) \mathrm{E} + 285(285^{-1} \mod 28) \mathrm{S} + 420(420^{-1} \mod 19) \mathrm{M}) \pmod{7980} \\ &\equiv& (532(7^{-1} \mod 15) \mathrm{E} + 285(5^{-1} \mod 28) \mathrm{S} + 420(2^{-1} \mod 19) \mathrm{M}) \pmod{7980} \\ &\equiv& (532 \times 13 \mathrm{E} + 285 \times 17 \mathrm{S} + 420 \times 10 \mathrm{M}) \pmod{7980} \\ &\equiv& (6916 \mathrm{E} + 4845 \mathrm{S} + 4200 \mathrm{M}) \pmod{7980} \end{matrix} $$

 

 

코드

E S M이 15 28 19인 경우도 처리할 수 있도록 한다.

import sys

e, s, m = map(int, sys.stdin.readline().split())
y = (6916 * e + 4845 * s + 4200 * m) % 7980
print(y if y else 7980)

 

---

참고 문서

https://casterian.net/algo/crt.html