취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4811번 문제인 알약이다.
문제는 아래 링크를 확인하자.

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

문제의 규칙을 만족하는 문자열의 개수는 카탈란 수와 같다는 점을 눈치채자.

이 특징은 주어진 문자열의 어떤 지점에서도 그 때까지 나온 H의 개수는 W를 넘지 못한다는 규칙을 통해 알아낼 수 있다.

따라서, 30까지의 카탈란 수를 출력하는 코드를 작성하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll comb[31][31];
ll ans[31];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i <= 30; i++) comb[i][0] = 1;
	for (int i = 1; i <= 30; i++) {
		for (int j = 1; j <= i; j++) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
	}

	ans[0] = 1;
	for (int i = 1; i <= 30; i++) {
		for (int j = 0; j < i; j++) {
			ans[i] += ans[j] * ans[i - j - 1];
		}
	}

	int x; cin >> x;
	while (x > 0) {
		cout << ans[x] << '\n';
		cin >> x;
	}
}