algorithm/dp
boj 15989 1, 2, 3 더하기 4
와이에쓰
2021. 1. 22. 22:00
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
제 개인적으로는 생각을 좀 해봐야했던 dp문제였습니다 ㅠㅠ.. 오래안해서 다죽은듯..
처음에는 방법의 수를 하나하나 나열해봤지만 해답을 찾을수 없었는데..
1, 2, 3으로 나타내는 방법의 수를 나누는 방법을 생각해보았습니다.
1. 1이하의 수로 나타내는 방법
2. 2이하의 수로 나타내는 방법
3. 3이하의 수로 나타내는 방법
으로 나눌 수 있습니다.
1이하로 나타내는 방법은 i - 1번째의 1이하로 나타내는 방법과 같습니다.
2이하로 나타내는 방법은 i - 2번째의 1이하로 나타내는 방법 + 2이하로 나타내는 방법입니다.
3이하로 나타내는 방법은 i - 3번째의 1이하로 나타내는 방법 + 2이하로 나타내는 방법 + 3이하로 나타내는 방법입니다.
따라서 dp[0][N], dp[1][N], dp[2][N]을 모두 더한 값이 답이 되겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <iostream>
using namespace std;
int dp[3][10001];
void init() {
dp[0][1] = 1;
dp[0][2] = 1;
dp[1][2] = 1;
dp[0][3] = 1;
dp[1][3] = 1;
dp[2][3] = 1;
for (int i = 4; i <= 10000; i++) {
dp[0][i] = dp[0][i - 1];
dp[1][i] = dp[0][i - 2] + dp[1][i - 2];
dp[2][i] = dp[0][i - 3] + dp[1][i - 3] + dp[2][i - 3];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
int tc, N;
cin >> tc;
while (tc--) {
cin >> N;
cout << dp[0][N] + dp[1][N] + dp[2][N] << '\n';
}
return 0;
}
|
cs |