백준/DP
(c++)백준 15989번: 1, 2, 3 더하기 4
Nimgnoej
2020. 9. 14. 20:33
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
[풀이]
DP로 풀 수 있는 문제였다.
중복을 피하기 위해 오름차순으로만 더한다.
DP[i][1]: 정수 i를 만들 때 1로 끝나는 경우 -> 그 이전에 1만 올 수 있다.
DP[i][2]: 정수 i를 만들 때 2로 끝나는 경우 -> 그 이전에 1과 2가 올 수 있다.
DP[i][3]: 정수 i를 만들 때 3으로 끝나는 경우 -> 그 이전에 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]
#include <iostream>
#define Max 10001
using namespace std;
int DP[Max][4] = { 0, };
int curN = 0;
int T;
void solution() {
DP[0][1] = 1;
DP[1][1] = 1;
for (int i = 2; 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 main() {
int n;
cin >> T;
solution();
curN = 3;
while (T--) {
cin >> n;
cout << DP[n][1] + DP[n][2] + DP[n][3] << '\n';
}
return 0;
}