[BOJ] 9095. 1,2,3 더하기(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

1. DP idx 정의

- dp[i]는 i를 1,2,3의 합으로 나타내는 방법의 수

2. 점화식 구하기

N = 

0 : 0 

1 : 1 (1)

2 : 2 (1+1, 2)

3 : 4 (1+1+1, 2+1, 1+2, 3)

4 : 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)

...

[0, 1, 2, 4, 7 ... ]

점화식을 찾아보자.

두구두구두구...!!!

dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 로 구할 수 있다.

사실 저 규칙만으로 점화식을 찾기가 쉽진 않다.

그래서 여러 점화식을 세워보고 적용해보는게 좋을 것 같다.

3. 시간복잡도 계산

O(N)만에 가능하다.

#. Code

#include <cstdio>
 
int dp[12] = { 0, 1, 2, 4, };
 
int main(void)
{
    int tc, n, i;
    scanf("%d", &tc);
 
    for (i = 4; i <= 12; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
    while (tc--) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
 
    return 0;
}

line 3) 직관적으로 구할 수 있는 작문 문제의 해를 구해놓는다.

line 10~11) n이 11보다 작다고 하였으므로, 미리 해를 구해놓은 후 작업

line 11) 점화식 적용!

line 15) 미리 해를 구해놓았으니 가져다 쓰기만 하면 된다.