[1476번] 날짜 계산

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

1476번: 날짜 계산

 

이 문제는 두가지 방법으로 풀어보았습니다.

그러나 맥락은 결국 같은 방법인데, 모든 경우의 수를 다해보는 것입니다.

모든 경우의 수를 다 따져보는 것을 브루트 포스(Brute force) 알고리즘이라고 합니다.

 

 

[코드1]

첫번째 방법은 E, S, M을 계속 증가시켜보면서 입력으로 주어진 e, s, m과 일치하는 경우 그때의 년도(i)를 출력하는 것입니다.

최대 년도는 문제에서 주어진 e, s, m의 제한 값을 전부 곱한 값이 됩니다.

#include <iostream>
using namespace std;
int main() {
    int e, s, m; 
    cin >> e >> s >> m;
    int E = 0, S = 0, M = 0;
    for(int i = 1; i <= 15*28*19; i++) {
        E++; S++; M++;
        if (E == 16) E = 1;
        if (S == 29) S = 1;
        if (M == 20) M = 1;
        
        if (e == E && s == S && m == M) {
            cout << i << '\n';
            break;
        }
    }
    return 0;
}

 

 

[코드2]

두번째 방법은 나머지 연산을 이용하는 것인데요. 이것 또한 브루트포스입니다.

입력으로 들어온 e, s, m을 나머지 연산시 답이 떨어지도록 1씩 빼줍니다. 그리고 구하고자 하는 시작년도를 0으로 정합니다.

이유는,

예를 들면 정답이 15년일 경우 입력으로 주어지는 e, s, m의 값은 15, 15, 15 입니다.

정답 년도 값에서 1을 뺀 수 14를 15, 28, 19로 각각 나눈 나머지를 확인해보면

14 % 15 = 14

14 % 28 = 14

14 % 19 = 14

14, 14, 14가 되는데 이는 입력으로 주어진 e, s, m 값에서 1을 뺀 값입니다.

그러므로 나머지 연산에 편리하도록 애초에 e, s, m 에서 1을 뺀 후에, 0부터 정답 년도를 전부 조사해가면서 나머지 연산의 결과가 e, s, m과 일치하는지 확인합니다.

그리고 실제 년을 출력할 때 1을 더해주면 올바른 답을 구할 수 있습니다.

#include <iostream>
using namespace std;
int main () {
    int e, s, m;
    cin >> e >> s >> m;
    e--;
    s--;
    m--;
    
    for (int i = 0; ; i++) { //0년부터 1년씩 증가하면서 i를 체크
        if(i % 15 == e && i % 28 == s && i % 19 == m) {
            cout << i + 1 << '\n';
            break;
        }
    }
    return 0;
}

 

[결과]

두 코드의 결과는 동일합니다.

1 16 16
16