728x90
반응형
https://www.acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
#include <iostream>
using namespace std;
int main() {
long long dp[10001][4] = { 0, };
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][3] = 1;
for(int i = 3; i <= 10000; i++){
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
if(i > 3) dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
}
int t, n;
cin >> t;
for(int i = 0; i < t; i++){
cin >> n;
cout << dp[n][1] + dp[n][2] + dp[n][3] << '\n';
}
return 0;
}dp[i][1]: 정수 i를 만들 때 1만 더하는 경우
dp[i][2]: 정수 i를 만들 때 1, 2만 더하는 경우
dp[i][3]: 정수 i를 만들 때 1, 2, 3을 더하는 경우
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3]
728x90
반응형
'Algorithm > BAEKJOON' 카테고리의 다른 글
| [BOJ] 24444번, 24445번 알고리즘 수업 - 너비 우선 탐색 1, 2 (C++) (0) | 2022.02.15 |
|---|---|
| [BOJ] 24479번, 24480번 알고리즘 수업 - 깊이 우선 탐색 1, 2 (C++) (0) | 2022.02.15 |
| [BOJ] 16165번 걸그룹 마스터 준석이 (C++) (0) | 2022.02.14 |
| [BOJ] 3495번 아스키 도형 (C++) (0) | 2022.02.13 |
| [BOJ] 21966번 (중략) (C++) (0) | 2022.02.13 |
