4811 ์์ฝ
์๊ณ ๋ฆฌ์ฆ (dp)
1. ํ๋์ ์์ ํ ์์ฝ์ one, ๋ฐ์ชฝ ์์ฝ์ half ๋ผ๊ณ ํ๋ฉด, dp[1001][1001] ๋ฅผ ์ ์ธํ๊ณ , one, half๋ฅผ ๊ธฐ์ค์ผ๋ก dp๋ฅผ ์ ์ฅํจ
2. dp๋ฅผ ์งํํ๋ฉด์ ๋ฐ์ผ๋ก ๋ด๋ ค๊ฐ๋ฉด์ one์ด 1๊ฐ ์ด์์ด๋ฉด 1 ์ค์ด๊ณ half 1 ์ฆ๊ฐํ๊ณ ๋ฐ์ผ๋ก ๋ด๋ ค๊ฐ ์ ์๊ณ , half๊ฐ 1๊ฐ ์ด์์ด๋ฉด ๋ง์ฐฌ๊ฐ์ง๋ก.
์ฝ๋
#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;
}