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

전형적인 DP 문제로, 점화식만 이끌어 낸다면 쉽게 풀 수 있다.

• n번째에서의 경우의 수를 계산한다 하자
• n-1에서 n으로 가는 경우의 수는 한가지다.
• n-2에서 n으로 가는 경우는 n-2+1+1, n-2+2로 2가지다. 이때 n-2+1+1은 n-1에서 n으로 갈 떄 세준 케이스 이므로 n-2+2 의 한가지 경우만 센다.
• 마찬가지로 n-3에서 n으로 가는 경우의 수도 한가지이다.

즉, 다음과 같이 식을 세울 수 있다.

 

DP[n]=func(n-1)+func(n-2)+func(n-3)

 

스스로 코드를 짠 후 아래를 눌러 읽어보자.

#include <iostream>

using namespace std;

int DP[11];

int func(int n) {
    if(DP[n]) return DP[n];
    if(n==1) return DP[n]=1;
    if(n==2) return DP[n]=2;
    if(n==3) return DP[n]=4;
    return DP[n]=func(n-1)+func(n-2)+func(n-3);
}

int main() {
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        cout << func(x) << endl;
    }
}