백준 9095번 - 1, 2, 3 더하기(C++)

문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

문제 풀이

---

#include <iostream>
using namespace std;

// 동적 계획법을 사용
int count(int n) {
    int dp[12] = {0}; // 1부터 11까지의 경우를 저장할 배열

    // 초기값 설정
    dp[1] = 1;
    dp[2] = 2; //1 + 1, 2
    dp[3] = 4; // 1+1+1, 1+2, 2+1, 3.
               // dp[3] + dp[2] + dp[1];

    for (int i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    return dp[n];
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        cout << count(n) << endl;
    }

    return 0;
}

dp[1] = 1
dp[2] = 2 // 1+1, 2
dp[3] = 4 // 1+1+1, 1+2, 2+1, 3
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
=> dp[i-1] 에서 1 더하는 경우 + dp[i-2]에서 2 더하는 경우 + dp[i-3]에서 3 더하는 경우 (단, i > 3)