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

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int main(void) {
5  int arr[11] = {1, 2, 4, 7};
6  for(int i=4; i<11; ++i)
7    arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
8  
9  int t;
10  cin >> t;
11  while(t--) {
12    int v; 
13    cin >> v;
14    cout << arr[v-1] << endl;
15  }
16  return 0;
17}