[9095번] 1, 2, 3 더하기

문제

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

 

문제접근법.

 

규칙을 발견해야 문제를 해결할 수 있다. 점화식만 보고 직관적으로 이해가 되면 좋겠지만, 대부분이 그렇지 않을 것이다. n = 4 라는 예제를 통해서 이해도를 높여보자.

 

n >= 4 일 때,

f(n) = f(n - 1) + f(n - 2) + f(n - 3)이다. 

 

n = 1 일 때, 1

n = 2 일 때, 1 + 1 / 2

n = 3 일 때, 1 + 1 + 1 / 2 + 1 / 1 + 2 / 3

n = 4 일 때, 1 + 1 + 1 + 1 / 1 + 1 + 2 / 1 + 2 + 1 / 2 + 1 + 1 / 3 + 1 / 3 + 1

과 같다,

 

n = 1일 때, 3을 붙이고 n = 2일 때, 2를 붙이고, n = 3일 때 1을 붙이면 n = 4 일 때 조합을 만들 수 있다.

 

해설코드(C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int dp[11];
int N, num;
int result = 1;
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 11; i++) {
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    }
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        cout << dp[num] << endl;
    }
}