1, 2, 3 더하기
링크
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 26256 | 16688 | 11400 | 62.230% |
문제
정수 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
1
2
3
4
3
4
7
10
예제 출력 1
1
2
3
7
44
274
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main(){
int dp[11]={0};
dp[0]=1; dp[1]=1; dp[2]=dp[0]+dp[1];
for(int i=3;i<11;i++)
dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
int t ; cin >> t;
while(t--){
int n; cin >> n;
cout << dp[n] <<'\n';
}
}