BOJ 1924 - 2007년 DP(memoization) 초기화

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	49902	20512	17700	43.073%

문제

오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다.

출력

첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT중 하나를 출력한다.

전략

1. 입력으로 들어온 월과 일에 대해서, 2007년 1월 1일 기준으로 상대적인 일수로 표현

2. 일수를 기준으로, mod연산을 통해 요일로 변환.

3. 변환 된 요일을 switch문을 통해 상응하게 출력.

2,3 번의 경우 1번 조건만 잘 해결 된다면 바로 구현이 되므로, 사실상 1번을 해결하는 것이 위 문제의 해결과제였다.

1의 문제를 다시 분해해보면 아래와 같다.

(1) 입력으로 받은 달을 기준으로 이전 달에 대한 경과 일수 확인

(2) (1)에 일수 더하기

결국, 이 문제 전체에서 핵심은 이전달에 대한 누적된 일수를 측정하는 것에 있었다.

문제에서 각 달에 대한 일수 정보를 알려줬으므로, 이를 각 배열에 할당할 수 있다. 

문제는 요청이 발생할때 마다, 각 달별 누적된 일의 수를 측정하는 것은 불필요한 연산이 발생 할 수 있다.

가령 3월에 대한 누적된 일 수를 구할때는 1,2월을 구해야되고, 5월에 대한 누적된 일수를 구할땐, 1,2,3,4월에 대한 일수를 합산한다.

이 과정에서 재귀적인 연산을 확인할 수 있다.

만약, 브루트 포스 방식에 재귀함수를 통해 초기화를 진행한다면, 월이 n이라면, 각 달에 대한 누적일 수를 구할때의 복잡도가 O(n^2)이 된다.

여기에서, memoization을 활용하면, 복잡도를 O(n)로 만들 수 있다.

n월 이전달까지 누적된 일수를 합산하는 배열을 MD[n]라하고, 각 달의 일수를 M[n]이라고 하자.

MD[n] = MD[n-1] + M[n] 이 성립한다.

bottom - up 방식을 통해 초기화하면,

위와 같다.

#include <iostream>
 
using namespace std;
 
int main(void)
{
    int Month,Day;
    int MD[11] = { 0, };
    int Months[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    MD[0] = 31;
    for (int i = 1; i < 11; i++) 
    {
        MD[i] = MD[i - 1] + Months[i];
    }
    
    cin >>Month >>Day;
 
    if (Month > 1)
        Day += MD[Month - 2];
 
    switch (Day % 7)
    {
 
        case 0:
            cout << "SUN" << '\n'; 
            break;
        case 1:
            cout << "MON" << '\n';
            break;
        case 2:
            cout << "TUE" << '\n';
            break;
        case 3:
            cout << "WED" << '\n';
            break;
        case 4:
            cout << "THU" << '\n';
            break;
        case 5:
            cout << "FRI" << '\n';
            break;
        case 6:
            cout << "SAT" << '\n';
            break;
    }
    return 0;
}