2226 이진수

0 을 10 으로, 1을 01로 치환하면서 N번 반복할 때, 연속인 0의 그룹의 수를 구하는 문제이다.

처음엔 단순히 문자열로 수열을 구현해줬는데 입력이 1000까지여서
2^1000 의 길이가 필요하다는것을 깨달았다. 물론 구현 불가능하다.

규칙을 살펴보니 다음과 같은 점화식이 보엿다.
f(n) = f(n-1) + 2*f(n-2)
그런데 이렇게 구현해주어도 문제가 생겼다. 입력이 1000까지라 값이 long long 형을 넘어버리는 것.

따라서 큰수의 연산을 구현해줄 필요가 있었다.
즉, 위 점화식을 큰수 연산으로 구해주면 된다.

소스