백준/DP

[백준 9095, c++] 1,2,3 더하기(dp: topDown, bottomUp)

전두선 2019. 11. 27. 16:32
문제 번호
문제 및 입/출력

정수 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

 

문제 풀이

Dynamic Programming(DP)를 통해 간단히 풀 수 있는 문제이다. 

 

점화식을 구하기 위해 n을 5까지 나올 수 있는 경우의 수를 구했다.

 

n = 1, cnt = 1;

n = 2, cnt = 2;

n = 3, cnt = 4;

n = 4, cnt = 7;

n = 5, cnt = 13

....

그 결과 규칙이 보였고, 규칙으로 아래와 같은 점화식을 만들 수 있었다.

-> 점화식 : D[n] = D[n-1] + D[n-2] + D[n-3]

 

문제는 topDown 방식과 bottomUp 방식을 둘 다 이용해서 풀어 보았다.

소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
#define MAX 11
 
int Dp[MAX];
 
int topDown(int n) {
    if (n == 1return 1;
    if (n == 2return 2;
    if (n == 3return 4;
 
    return topDown(n - 1+ topDown(n - 2+ topDown(n - 3);
}
 
int bottomUp(int n) {
    Dp[1= 1;
    Dp[2= 2;
    Dp[3= 4;
 
    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,n;
    scanf("%d"&t); // test case
 
    while (t--) {
        scanf("%d"&n);
 
        //int result = topDown(n);
        int result = bottomUp(n);
 
        printf("%d\n", result);
    }
    return 0;
}
 
 
/*
n = 1, cnt = 1;
n = 2, cnt = 2;
n = 3, cnt = 4;
n = 4, cnt = 7;
n = 5, cnt = 13
....
점화식 : D[n] = D[n-1] + D[n-2] + D[n-3]
*/