4811 알약

통에 N개의 알약이 들어있다. 여기서 하나의 알약을 꺼내면 반절만먹고 반절은 다시 넣는다. 반절짜리 알약을 꺼내면 다 먹는다. 이 때 하나의 알약을 꺼내는 경우 W, 반절짜리를 꺼내는 경우 H를 출력한다 할 때, 출력되는 문자열의 경우의 수를 구하는 문제이다.

이 문제는 점화식이 매우 간단하다.
F(w,h) = F(w-1,h+1) + F(w,h-1)

여기까진 쉽게 떠올랐고 당연히 DP로 풀면 금방이다.

그러나 본인은 이 점화식을 DP로 생각하지 못하고 노가다에 노가다를 거듭하여 점화식을 풀어냈다.

F(n) = (2n)! / (n! * (n+1)!)

아래 식을 이용하여 답을 구했는데, 이것도 자꾸 오버플로우가 일어나기 때문에 최대공약수를 이용하여 조금씩 값을 증가시켰다.

상당히 서러운 문제였다.

소스