[BOJ][DP]9005 1,2,3 더하기

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

이 문제는 규칙을 파악하는 문제다.

필자도 아무리 생각해도 갈피를 못 잡아 인터넷 참고를 조금 했다.

- 풀이 - 

n = 1 일때, ( 1 )로, 경우의 수는 1개.

n = 2일때, (1 + 1), ( 2 )로, 경우의 수는 2개.

n = 3일때, (1 + 1 + 1), (1 + 2), (2 + 1), ( 3 )으로 경우의 수는 4개. 

n = 4는 문제 예시에 나와있으므로 7개.

어라? n = 1~3 까지의 경우를 더한게 n = 4의 경우의 수랑 같네?

위의 사실로는 n[i] = n[i-3] + n[i-2] + n[i-1] 과 같다.

우연일지도 모른다. 그래서 일단 위의 가설을 전제로 n = 7까지 계산해보자.

n = 5, 13개 

n = 6, 24개.

n = 7, 44개.

어? n = 7일 때의 경우의 수가 입력 예제의 n = 7과 같네?

그럼 확정 됬다. 

이 문제의 점화식은, 각 n 값마다의 경우의 수를 dp[i]라고 할때,

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

가 되시겠다.

이번엔 실마리를 봐버렸지만, 다음번에는 꼭 규칙을 깨닫기를..

#include <iostream>
 
int dp[12] = {0, 1, 2, 4, };
 
void DP()
{
    for (int i = 4; i <= 12; i++)
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    return;
}
 
int main()
{
    DP();
    int T;
 
    std::cin >> T;
 
    int temp;
    for (int i = 1; i <= T; i++)
    {
        std::cin >> temp;
        std::cout << dp[temp] << std::endl;
    }
 
    return 0;
}