Study hard
(c++)백준 9095번: 1, 2, 3 더하기 본문
https://www.acmicpc.net/problem/9095
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의 합으로 나타내는
www.acmicpc.net

※점화식※
dp[x] : x를 1,2,3의 합으로 나타내는 방법의 수
dp[1] = 1 (1)
dp[2] = 2 (2, 1+1)
dp[3] = 4 (1+1+1, 1+2, 2+1, 3)
x번째 값은 x-3번째 값에 +3을 하거나, x-2번째 값에 +2를 하거나, x-1번째 값에 +1을 하므로,
dp[x] = dp[x-3] + dp[x-2] + dp[x-1]이 된다.
#include <iostream>
using namespace std;
int T, n;
int dp[11];
int cnt = 4;
void DP() {
for (int i = cnt; i <= n; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
cnt = n + 1;
cout << dp[n] << endl;
}
int main() {
cin >> T;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
while (T--) {
cin >> n;
//이전 테스트케이스에서 이미 구한 값이면 바로 출력
if (n < cnt) {
cout << dp[n] << endl;
continue;
}
DP();
}
return 0;
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 11057번: 오르막 수 (0) | 2020.06.08 |
---|---|
(c++)백준 10844번: 쉬운 계단 수 (0) | 2020.06.08 |
(c++)백준 11727번: 2xn 타일링 2 (0) | 2020.06.08 |
(c++)백준 11726번: 2xn 타일링 (0) | 2020.06.08 |
(c++)백준 1463번: 1로 만들기 (0) | 2020.06.08 |