[동적 계획법 : 다이나믹 프로그래밍] BOJ 9095 1,2,3 더하기

다이나믹 프로그래밍 문제집에 속한 문제를 풀고있습니다

참고: https://www.acmicpc.net/workbook/view/7319

문제집: 0x10강 - 다이나믹 프로그래밍 (BaaaaaaaaaaarkingDog)

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

시간제한: 1초

풀이

A(n)

- A(n-1), 즉 n-1을 만드는 모든 경우 각각에 대해 그 뒤에 1을 더하는 것과

- A(n-2), 즉 n-2를 만드는 모든 경우 각각에 대해 그 뒤에 2를 더하는 것과

- A(n-3), 즉 n-3을 만드는 모든 경우 각각에 대해 그 뒤에 3을 더하는 것

의 모든 경우의 수의 합이다.

그래서 1,2,3 까지 배열을 정의해두고 점화식을 통해 풀면 된다.

 

간단한 문제이기 때문에 코드를 바로 정리해보면 다음과 같다.

#include <iostream>
using namespace std;
int main() {
    int T;
    cin >> T;
    int dp[10] = {0,1,2,4};
    for(int i = 4; i< 11; i++){
     dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    }
    for(int i = 0; i < T ;i++){
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
    return 0;
}