#1476 날짜 계산

이번 문제는 난이도는 Silver V로 쉬운 편입니다.

 

수학적 지식을 가지고 있다면 손쉽게 풀 수 있습니다.

 

E, S, M 이란 단위가 1부터 시작해서 각각 15, 28, 19 의 범위를 가지는데, 모두 같이 증가하기 시작해서 16이 되면 E의 값은 1이 됩니다.

 

즉 다음과 같이 움직이게 되죠.

1 1 1 -> 2 2 2 -> 3 3 3 -> ... -> 15 15 15 -> 1 16 16 -> 2 17 17 -> ... -> 4 19 19 -> 5 20 1 -> ...

 

우리가 얻고자 하는 숫자가 x년도라면, E, S, M은 다음과 같이 표현할 수 있습니다.

\[ ( (x-1)~ mod~ 15 + 1, (x-1)~ mod~ 28 + 1, (x-1)~ mod~ 19 + 1 ) \]

 

15, 28, 19 는 서로 소인 숫자이므로, 최대 표현할 수 있는 숫자는 15*28*19 = 7980입니다.

 

이것을 이해하시려면 중국인의 나머지 정리를 아시면 좋습니다.  중국인의 나머지 정리를 이용하면 이 문제의 답을 쉽게 풀 수 있죠.

최대로 표현할 수 있는 수는 7980입니다.

 

\[ x = a \cdot E + b \cdot S + c \cdot M \]

 

형태로 계산할 수 있다고 해보죠.  그러면 이 식을 15로 나누게 된 나머지는

\[ E = a \cdot E~ mod~ 15 \]

 

형태가 되어야 합니다.  S와 M에는 영향 받으면 안 되니까요.  즉, b, c는 15의 배수여야 합니다.

a 값은 그러면 어떻게 되어야 할까요?  a = 28 x 19 x a' 형태어야 하고, a'은 mod 15에 대해서 \( (28 \cdot 19)^{-1}~ mod~ 15 \)가 되어야 합니다.  그 값이 13이 됩니다.  마찬가지로 b'은 17, c'은 10이 됩니다.

 

그래서 우리는 x값을 다음과 같이 구할 수 있습니다.

\[ x = 28 \cdot 19 \cdot 13 \cdot E + 15 \cdot 19 \cdot 17 \cdot S + 15 \cdot 28 \cdot 10 \cdot M \]

그런데 7980을 넘지 말아야 하기 때문에 \( (x-1)~ mod~ 7980 + 1 \)로 표현해주면 됩니다.

 

이것을 프로그램으로 바꾸면 다음과 같습니다.  소스는 참조용으로만 봐주세요.

//--------------------------------------------------------------------
//    baekjoon #1476
//        - by Aubrey Choi
//        - created at 2019-07-03
//--------------------------------------------------------------------
#include <stdio.h>

//    15*28*19 = 7980
//    28*19^-1 = 13, 15*19^-1 = 17, 15*28^-1 = 10
int main()
{
    int e, s, m, x;
    scanf("%d%d%d", &e, &s, &m);
    x = 28 * 19 * 13 * e + 15 * 19 * 17 * s + 15 * 28 * 10 * m;
    x = (x - 1) % 7980 + 1;
    printf("%d\n", x);
    return 0;
}