#265 백준 파이썬 [2193] 이친수 - 피보나치 수열

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

 

Solution

이친수를 한 자리 수 부터 써나가다보면 특징을 알 수 있다.

N이 6일때를 보자

	1	2	3	4	5	6
1	1	10	100	10000	10000	100000
2			101	1010	10100	101000
3				1001	10010	100100
4					10001	100010
5					10101	101010
6						100001
7						101001
8						100101

N이 6일때 빨간 부분으로 표시한 숫자는 5열의 숫자를 그대로 가져와서 뒤에 0만 더해주었다.

N이 6일때 파란 부분으로 표시한 숫자는 4열의 숫자를 그대로 가져와서 뒤에 01만 더해주었다.

다시 말해 이친수(N)은 N-1과 N-2를 더한 값이다.

따라서 피보나치 수열을 따르는 값을 가진다. (1-1-2-3-5-8...)

Python Code

N = int(input())

#피보나치 수열과 같다
if N == 1:
    print(1)
elif N == 2:
    print(1)
    
else:
    temp_1 = 1
    temp_2 = 1
    current = 0
    for _ in range(N-2):
        current = temp_1 + temp_2
        temp_1 = temp_2
        temp_2 = current
    print(current)