[C/C++ 백준 4811번] 알약 (Gold 5)

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

4811번: 알약

W가 N개, H가 N개로 이루어진 2N개 짜리의 문자열을 몇 개 만들 수 있는지 구하는 문제이다. 그러나 알약을 반으로 쪼개기 전에는 반쪽짜리를 먹을 수 없기 때문에 항상 문자열에서 W의 개수가 H의 개수보다 많아야 한다.

 

길찾기 문제에서 대각선 위쪽으로 움직이는 경우를 항상 고려해주면 된다.

아니면 그냥 DP 이차원 배열을 만들어준뒤 i가 W의 개수, j가 H의 개수로 하여 특정 조건만 집어넣어 주면 된다.

 

#include <cstdio>
#include <cstring>
using namespace std;
long long int DP[32][32];
int main(void){
	int n, N;
	memset(DP, 0, 32*32*sizeof(long long int));
	DP[1][1]=1;
	for(int i=1; i<=31; i++){
		for(int j=1; j<=31; j++){
			if(i>j)
				DP[i][j] = 0;
			else if(!(i==1 && j==1))
				DP[i][j] = (DP[i-1][j] +DP[i][j-1]);
		}
	}
	while(1){
		scanf("%d", &N);
		if(N==0)
			break;
		else
			printf("%lld\n", DP[N+1][N+1]);
	}
}