4811 알약
알고리즘 (dp)
1
2
1. 하나의 완전한 알약을 one, 반쪽 알약을 half 라고 하면, dp[1001][1001] 를 선언하고, one, half를 기준으로 dp를 저장함
2. dp를 진행하면서 밑으로 내려가면서 one이 1개 이상이면 1 줄이고 half 1 증가하고 밑으로 내려갈 수 있고, half가 1개 이상이면 마찬가지로.
코드
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
#include <iostream>
using namespace std;
long long dp[1001][1001];
long long DP(int one, int half);
int main() {
int N;
while (true) {
cin >> N;
if (N == 0)
break;
cout << DP(N, 0) << endl;
}
}
long long DP(int one, int half) {
if (one == 0 && half == 0)
return 1;
if (dp[one][half] != 0)
return dp[one][half];
long long result = 0;
if (one > 0)
result += DP(one - 1, half + 1);
if (half > 0)
result += DP(one, half - 1);
return dp[one][half] = result;
}