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 |
'algorithm > dp' 카테고리의 다른 글
| boj 15991 1, 2, 3 더하기 6 (0) | 2021.01.22 |
|---|---|
| boj 15990 1, 2, 3 더하기 5 (0) | 2021.01.22 |
| boj 15988 1, 2, 3 더하기 3 (0) | 2021.01.22 |
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |
| boj 9095 1, 2, 3 더하기 (0) | 2021.01.22 |