BOJ 1476. 날짜 계산

• 문제링크 : https://www.acmicpc.net/problem/1476

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (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이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

1. 문제 해석

이 문제는 E S M 연도 표기법으로 주어진 연도가 우리가 알고 있는 연도로 몇 년인지 구하는 것이다. 예를 들어, 1년은 E S M 연도로 1 1 1 이고, 2년은 2 2 2, 3년은 3 3 3, ... , 15년은 15 15 15 이다. 16년이 되면 E는 1로 초기화 되지만 나머지는 아직 초기화 되지 않아서 1 16 16 이 된다. 또 17년은 2 17 17, 18년은 3 18 18, 19년은 4 19 19, 20년은 M이 1로 초기화 되어서 5 20 1이 될 것이다.

이렇게 E S M 연도가 주어지면 1부터 E, S, M 값을 각각 증가시키면서 범위를 넘어가면 초기화 해주는 방식으로 구하면 될 것이다. 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이므로, E, S, M 변수를 각각 따로 두고 각 값을 1씩 증가 시키면서 E는 15가 넘어가면 1로 초기화, S는 28이 넘어가면 1로 초기화, M은 19가 넘어가면 1로 초기화 해주면 될 것이다.

이 풀이 방법의 시간 복잡도는 E S M 연도의 모든 경우를 다 구해보는 것일 것이다. e, s, m이라는 각각의 변수를 두고 각각 증가시키면 되기때문에 시간복잡도는 O(N)이다. 그리고 E S M 연도를 모두 구해보는 경우의 수는 15 x 28 x 19 = 7,980이다.

---

2. 문제 풀이

이 문제를 풀이하는 방법은 여러 가지가 있을 수 있다.

• 첫 번째로 e, s, m 각 변수를 두고 반복문 내에서 1씩 값을 증가시키다가 각 한계값을 넘으면 1을 대입하여 초기화 해주는 방식이다.

• 두 번째로 나머지 연산을 활용하는 방법이다. e, s, m을 1씩 증가시키면서 각 한계값으로 매번 나머지 연산을 해주는데, 이때 한계값과 같을때 0이 되어버리기 때문에 그때는 1이 되도록 예외처리를 해주어야 한다. 아니면 미리 주어진 E S M 연도에 -1을 모두 해주어서 나머지 연산을 하고 +1을 해주는 방식으로 구현 가능하다. (e-1) % 15 + 1, (s-1) % 28 + 1, (m-1) % 19 + 1 을 구하는 것이다.

• 마지막으로, 중국인의 나머지정리를 활용하며 풀 수도 있다.

변수에 대입을 통한 초기화

#include <iostream>
using namespace std;
int main() {
    int E, S, M;
    cin >> E >> S >> M;
    int e=1, s=1, m=1;
    for (int i=1;; i++) {
        if (e == E && s == S && m == M) { // 주어진 E S M 연도와 같다면 중지 
            cout << i << '\n';
            break;
        }
        e++; s++; m++; // 각 연도를 1씩 증가 
        if (e == 16) e = 1; // 한계값을 넘으면 1을 대입하여 초기화 
        if (s == 29) s = 1; // 한계값을 넘으면 1을 대입하여 초기화 
        if (m == 20) m = 1; // 한계값을 넘으면 1을 대입하여 초기화 
    }
    return 0;
}

나머지 연산을 통한 비교

#include <iostream>
using namespace std;
int main() {
    int e,s,m;
    cin >> e >> s >> m;
    e -= 1; s -= 1; m -= 1; // 미리 -1을 해준다. 
    for (int i=0;; i++) { // 계속 증가하면서 나머지 연산한 값과 비교하여 같다면 
        if (i % 15 == e && i % 28 == s && i % 19 == m) { 
            cout << i+1 << '\n'; // +1한 값을 출력 
            break;
        }
    } 
}				

중국인의 나머지 정리

중국인의 나머지 정리를 이용한 풀이는는 E S M을 1씩 증가시키는 것이 아니라, year을 mod연산하는 수 16, 28, 19에 대해서 유일한 해를 찾는 방식이다.

• year (mod 16) == E
• year (mod 28) == S
• year (mod 19) == M

위와 같은 연립 합동식은 16, 28, 19가 서로소이므로 16 x 28 x 19 = 7980에 대하여 유일한 해를 갖는다. 사실 이 문제를 풀기위해 중국인의 나머지 정리를 사용하는 것은 너무 비효율적이다..

#include <iostream>
using namespace std;
int main() {
    int e,s,m;
    cin >> e >> s >> m;
    cout << (6916*e + 4845*s + 4200*m - 1) % (15*28*19) + 1 << '\n';
    return 0;
}