백준/ Silver3 문제 , 백준 파이썬 2193 , 이친수

백준/ Silver3 문제 , 백준 파이썬 2193 , 이친수

 

 

<문제 출처>

 

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

2193번: 이친수

------------------------------------------------------------------------------------------------------------------------------

 

나올 수 있는 숫자들을 조금만 나열해보면 금방 규칙을 찾을 수 있다.

 

N=1 , 1  => 1개    

N=2 , 10 => 1개    

N=3 , 100, 101 => 2개

N=4 , 1000, 1001, 1010 =>  3개

N=5 , 10000, 10001, 10010, 10100, 10101, => 5개

N=6 , 100000, 100001, 100010, 100100, 101000, 100101, 101001, 101010 =>   8개

    . 

    .

    .

N=3 을보면 2개는 N=1, N=2 의 갯수를 더한것과 같고

 

N=4 를 보면 3개는 N=3, N=2 의 갯수를 더한것과 같다.

 

즉 N-1, N-2 의 값이랑 더한것과 같으니

 

이를 일반화 해보면

 

N=3 부터는

 

이 코드가 적용된다.

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답