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

문제 번호

• 9095(https://www.acmicpc.net/problem/9095)

문제 및 입/출력

정수 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 방식을 둘 다 이용해서 풀어 보았다.

소스 코드

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
#define MAX 11
 
int Dp[MAX];
 
int topDown(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 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]
*/