정답의 범위를 가늠하는 건 문제마다 제약조건이 천차만별일 테니, 이 문제에 국한해서 설명드려볼게요.

우선 n자리 이친수의 개수를 a_n이라 하고, 편의를 위해 이친수와 거의 같은 조건을 만족하되 0으로 시작하는 n자리 이진수의 개수를 b_n이라고 해 봅시다.

• a_n = (1이 연속으로 나타나지 않는 n자리 이진수 중 1로 시작하는 것의 개수)
• b_n = (1이 연속으로 나타나지 않는 n자리 이진수 중 0으로 시작하는 것의 개수)

그러면 a_n, b_n에 대한 점화식을 세울 수 있는데, 이 점화식은 결국 다음과 같은 형태를 가지게 될 것입니다.

• a_n+1 = b_n
• b_n+1 = a_n + b_n

이것을 다시 쓰면 결국

• v_n+1 = [ a_n+1 ] = [ 0 1 ] [ a_n ]  = Av_n
•            [ b_n+1 ]    [ 1 1 ] [ b_n ]

즉 행렬에 의한 곱으로 나타낼 수 있습니다. 이 행렬을 A라고 하고, 대각화(diagonalization)를 하여

• A = PDP^-1, D: diagonal matrix of eigenvalues

로 표현했다고 해 봅시다. 그러면

• v_n = Aⁿv₀ = PDⁿP^-1v0

이때 D는 diagonal matrix이므로 Dⁿ을 계산하기 위해서는 diagonal entry를 각각 n제곱하면 됩니다.

이렇게 하면, a_n은 v_n의 첫 번째 성분이고, 대략적으로 (v₀의 크기) x (D에서 절댓값이 가장 큰 eigenvalue의 절댓값) 정도의 크기를 가진다는 것을 알 수 있습니다.

결국 하고 싶었던 말은, coupled linear recurrence equation의 해는 계수행렬의 eigenvalue spectrum으로 그 growth를 가늠할 수 있다는 점입니다.

도움이 되셨기를 바랍니다!

위 분 답변에서 보듯 크기를 계산하는 데에는 종종 문제를 푸는 것보다 훨씬 더 많은 지식이 필요할 수 있습니다.

문제에서 제한이 주어져 있고, 그 제한이 어떤 범위에 들어가는지 알아보는 것으로 충분하다면, 그냥 최대 크기까지 돌려 보면서 범위를 넘어갈 수 있을 때 반복문을 멈추는 식으로 확인해볼 수 있습니다. 예를 들어 2^63 내에 답이 들어오는지 알고 싶다면, b_n > 2^63이기 위해서 b^n-1 > 2^62 혹은 a_n-1 > 2^62 중 하나는 성립해야 하니까, 두 조건에 걸리지 않을 때까지 반복문을 돌려 보고 그 때의 결과를 보는 식으로도 충분히 해결할 수 있습니다.