[백준 14556] Balance

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

 

이 문제를 읽고 생각한 뒤, 처음 생각한 점화식은 이거였다.

점화식: (n번째 추를 먼저 놓는다 가정했을 때)

$f(n)={\displaystyle\sum_{i=1}^{n}} \{_{n-1}\mathrm{P}_{i-1} 2^{i-1} f(n-i)\}, \; f(1)=1$

근데 이 풀이는 시간 초과가 났다. 가만 생각해 보니 $O(n^3)$ 이어서 시간이 상당히 오래 걸렸다.

 

살짝 발상을 바꾼 점화식) i번째 추를 마지막에 놓는다 생각한다면, n번째 추는 놓을 곳이 1군데밖에 없으므로 $f(n-1)$, i번째 추는 놓을 곳이 2군데이므로 $2f(n-1)$,  
이를 $1...n$까지 전부 더하면 $f(n-1)$이 $(2n-1)$개 있게 되므로,
$f(n)=(2n-1)f(n-1), \; f(1)=1 $
과도 나타낼 수 있다.

 

다른 말로 하자면 $1, 3, 5, ... 2n-1$까지의 홀수를 다 곱한 것이다
 $f(n)={\displaystyle\prod^n_{i=1}}(2i-1)$

또는
 $f(n)=\frac{(2n)!}{n!2^n}$

 

이 3개의 식은 모두 같은 뜻이며 $O(n)$에 동작한다.

생각의 순서만 바뀌었는데 풀이가 완전히 달라지는 게 개인적으로 재밌었던 문제였다.