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;
}