01타일
Prob
00또는 1을 이용한 N개 경우의 수
Solv
- 점화식 \(p=\frac{N}{2}\)
짝수
\(1+\displaystyle\sum^p_{k=1}\frac{(p+k)!}{(p-k+1)!(2k-1)!}\)
홀수
\(2+\displaystyle\sum^{p-1}_{k=1}\frac{(p+k)!}{(p-k)!(2k)!}\)
integer overflow - 피보나치
피보나치 규칙성이 있었음
dynamic programming으로 연산량 축소
Check
| 0 | 1 | 2 |
|---|---|---|
| 1 | 2 | 3 |
| 5 | 8 | 13 |
| 21 | 34 | 55 |
Feedback
경우의 수에 빠져 너무 복잡하게 생각했다. 수가 커질 때는 연산 중 integer overflow 발생 가능성을 염두해야 한다. 재귀보다는 dp를 사용하자.
