728x90
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>
#include<vector>
#include<cstring>
using namespace std;
int dp[10001][4];
void solve(int n, int k) {
if (dp[n][k]) { return; }
for (int i = 4; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
int sum = 0;
if (j == 1) {
dp[i][j] = 1;
continue;
}
else {
for (int m = 1; m <= j; m++) {
sum += dp[i-j][m];
}
}
dp[i][j] = sum;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
memset(dp, 0, sizeof(dp));
dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
cin >> n;
vector<int>answer;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
solve(num,3);
answer.push_back( dp[num][1] + dp[num][2] + dp[num][3]);
}
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << endl;
}
return 0;
}
어떤알고리즘 어떤논리로?
- 다이나믹 프로그래밍으로 풀었다.
- 예를 들어 4를 1,2,3 으로 나타낸다 했을때 먼저 1을 고를 경우를 dp[4][1], 먼저 2를 고를 경우는 dp[4][2], 먼저 3을 고를 경우는 dp[4][3]에 저장을 한다.
- 이때 dp[4][1] = 3에서 1을 먼저 고르는 경우의 개수 + 3에서 2를 먼저 고르는 경우의 개수 + 3에서 3을 먼저 고르는 경우의 개수 가된다.
- 따라서 dp[4][1]=dp[3][1]+dp[3][2]+dp[3][3]이되며 점화식으로 나타내면 dp[i][j]=dp[i-j][1]+dp[i-j][2]+dp[i-j][3] 이 된다.