백준: 2193 이친수

문제

2193번: 이친수

 

문제 풀이

 자리 수의 증가에 따라 다음과 같은 경우의 수를 확인할 수 있다.

자리 수	1	2	3	4	5
	1	10	101	1000	10000
			100	1001	10001
				1010	10010
					10100
					10101

즉, N에 따라 만족하는 이친수의 경우는 f(n) = f(n - 1) + f(n - 2)라는 것을 알 수 있다. 이를 코드로 구현하면 간단히 문제를 해결 할 수 있다.

 

코드

if __name__ == '__main__':
    n = int(input())
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    print(a)