정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
DP[0] = 0
DP[1] = 1
DP[2] = 2
DP[3] = 4
DP[4] = 7
DP[i] = DP[i-1] + DP[i-2] + DP[i-3]
이므로 그냥 배열에 채워두고 풀면 되는데 브루트포스로 풀어야하므로 PASS
재귀 사용
탈출 조건
1. sum == n: 횟수에 포함 시킴 (return 1)
2. sum > n: 횟수에 포함시키지 않음 (return 0)
rec(int n, int sum){
if (sum==n) return 1;
else if (sum > n) return 0;
else if rec(n, sum+1) + rec(n, sum+2) + rec(n, sum+3);
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int rec(int n, int sum) {
if (sum == n) return 1;
else if (sum > n) return 0;
else return rec(n, sum + 1) + rec(n, sum + 2) + rec(n, sum + 3);
}
int main() {
int tc;
scanf("%d", &tc);
for (int i = 0; i < tc; i++)
{
int n;
scanf("%d", &n);
printf("%d\n", rec(n, 0));
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int main() {
int dp[11] = { 0,1,2,4, };
int tc;
scanf("%d", &tc);
for (int i = 4; i < 11; i++)
{
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
for (int i = 0; i < tc; i++)
{
int n;
scanf("%d", &n);
printf("%d\n", dp[n]);
}
}