백준 4811 - 알약

문제 설명

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

https://www.acmicpc.net/problem/4811

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 알약을 먹는 서로 다른 순서의 개수를 구해야 한다.

알약은 총 두 종류이다.

전체 알약은 W로 알약 반개는 H로 나타낸다.

 

우선, 순서를 만들면서 무조건 지켜야 하는 규칙이 있다.

H는 W로부터 생겨난다는 것이다.

즉, W를 한 개를 선택해야 H가 하나 늘어난다.

 

그럼 W를 선택하거나 H를 선택하는 과정을 반복하며 순서를 만들면 된다.

dfs를 진행하며 선택가능한 W와 H를 추적하며 개수를 세면 된다.

단, W를 모두 선택했다면 더 이상 진행할 필요가 없다.

그 이후로는 모두 H가 선택될 것이기 때문이다.

또한, H가 0이라면 H를 선택할 수 없다.

 

이렇게 구해낸 개수를 dp[W][H]에 기록하며 불필요한 진행을 방지하면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<vector<long long>> dp(31, vector<long long>(31, 0));
long long ans = 0;

long long dfs(int w, int h) 
{
	if (h < 0) return 0;
	if (w == 0) return 1;

	long long& ret = dp[w][h];
	if (ret) return dp[w][h];

	ret = dfs(w - 1, h + 1) + dfs(w, h - 1);
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	while (cin >> N)
	{
		if (N == 0) break;

		cout << dfs(N, 0) << endl;
	}

	return 0;
}

---