[백준] 2193번 이친수 C/C++ 풀이

출처: https://www.acmicpc.net/problem/2193

 풀이

먼저 이친수를 계산하기 위한 경우의 수를 계산해보자.

 > n = 이친수의 자리수

    f(n) = 자리수에 따른 이친수의 개수

 

if) n = 1 -> f(n) = 1    if) n = 2 -> f(n) = 1

   1                          10

if) n = 3 -> f(n) = 2    if) n = 4 -> f(n) = 3

   101                      1010

   100                      1000

                              1001

 

 점화 관계 추론

1, 1, 2, 3... 식으로 수열이 늘어나고 있다.

이는 피보나치 수열의 관계와 같은 형식이라고 추측할 수 있다.

$$ f_{n} = f_{n-2} + f_{n-1} \: (단,\, f_{1} = 1, f_{2} = 1) $$ 

 

 C/C++ 풀이