[DP] 백준 9095번 - 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

1과 2, 3을 활용해 어떤 수의 합으로 표현하는 방법을 구하는 문제다.

 

예를 들어 4를 만들고자 할 때 어떻게 하면 될까?

1까지 1,2,3으로 만든 경우의 수에 3을 더하면 되는것과

2까지 1,2,3으로 만든 경우의 수에 2를 더하는 것,

3까지 1,2,3으로 만든 경우의 수에 1을 더하는 것의 총 합이 된다.

 

f(n)을 1,2,3의 합으로 n을 만드는 경우의 수라 하면 아래와 같은 점화식을 만들 수 있다.

f(n) = f(n-1) + f(n-2) + f(n-3) (n은 4이상의 자연수)

물론, 점화식의 기본인 초항설정이 매우 중요하다. 

(DP의 핵심은 점화식 도출과 점화식의 자료구조화)

 

이를 코드로 옮기면 아래와 같다.

 

#include <iostream>
#include <algorithm>
#define maxlen 11
using namespace std;
int DP[maxlen];
int N;
int main(){
    cin >> N;
    DP[1] = 1, DP[2] = 2, DP[3] = 4;
    for (int i = 4; i <= 10; i++){
        DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
    }
    int which;
    for (int i = 0; i < N; i++){
        cin >> which;
        cout << DP[which] << '\n';
    }
    return 0;
}