[Baekjoon] 백준 9095번 1,2,3 더하기(다이나믹프로그래밍)

9095번 1,2,3 더하기 문제 풀이

문제

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
  • '4' 입력 시 나타낼 수 있는 방법

      1+1+1+1
      1+1+2
      1+2+1
      2+1+1
      2+2
      1+3
      3+1

입력

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

출력

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

예제

입력
3
4
7
10

출력 
7
44
274

코드

#include<iostream>
#include<algorithm>
using namespace std;

int d[12];

int top_down(int n) {
    if (n == 0) return 1;
    if (n == 1)return 1;
    if (n == 2)return 2;
    return d[n] = top_down(n - 1) + top_down(n - 2) + top_down(n - 3);
}

void bottom_up(int n) {
    for (int i = 3; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2] + d[i - 3];
    }
}
int main() {
    int n,t;
    cin >> t;
    while (t--) {
        cin >> n;
        d[0] = 1;
        d[1] = 1;
        d[2] = 2;
        //top_down(n);
        bottom_up(n);
        cout << d[n] << '\n';
    }
    return 0;
}

해결방법

• 브루트포스로 풀었던 문제를 DP로 해결하였다.

입력	분해
1	1
2	1+1 / 2
3	1+1+1 / 2+1 / 1+2 / 3
4	1+1+1+1 / 2+1+1 / 1+2+1 / 3+1 / 1+1+2 / 2+2 / 1+3

• 1,2,3을 가지고 주어진 숫자를 만들어야 할 떄 위와 같은 경우의 수가 나온다.
• d[0]을 공집합으로 생각하면, 공집합도 하나의 경우의 수가 되기 때문에 d[0] = 1이다.
• 위 표처럼 분해된 결과를 보게 되면, 2는 1의 경우의 수에서 1을 더해서 만들 수 있는 수 + 본인(2)로 만들 수 있으며, 3은 2의 경우의 수에서 1을 더한 값과, 1의 경우의 수에서 2를 더한 결과 값, 본인(3)이 된다.
• 4는 3의 경우의 수에서 1을 더한 값, 2의 경우의 수에서 2를 더한 값, 1의 경우의 수에서 1을 더한 값이 된다.
• 즉 d[n] = d[n-1]+d[n-2]+d[n-3]이라는 점화식이 나오게 된다.