[백준] 2193번 문제 (이친수) 파이썬(Python) 풀이

n = int(input())
dp = [0, 1, 1, 2]

for i in range(4, 101):
    dp.append(dp[i - 1] + dp[i - 2])

print(dp[n])

 

자리수 n에 대하여 이친수의 개수를 표로 나타내면 아래와 같다.

n	n에 대한 이친수의 개수
0	0
1	1
2	1
3	2
4	3
5	5
6	8

표를 보면 숫자 3부터 dp[n] = dp[i - 1] + dp[i - 2] 식이 성립한다는 것을 알 수 있다.

따라서 dp에 0 ~ 3(또는 더 높은 수) 까지 미리 이친수의 개수를 할당해주고 위의 식으로 n까지 for문을 반복하면

이친수의 개수를 알 수 있다.