[BOJ] 2193 / 이친수 / Python

[BOJ] 2193 / 이친수 / Python

[BOJ] 2193 / 이친수 / Python

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

2193번: 이친수

 

풀이

경우의 수를 구하여 나열해 보았다.

N = 1 -> 1
N = 2 -> 10
N = 3 -> 100 101
N = 4 -> 1000 1001 1010
N = 5 -> 10000 10001 10010 10100 10101
N = 6 -> 100000 100001 100010 100101 100100 101000 101001 101010

 

경우의 수의 개수가 피보나치 수열이 됨을 확인 할 수 있다.

N = 1 -> 1
N = 2 -> 1
N = 3 -> 2
N = 4 -> 3
N = 5 -> 5
N = 6 -> 8

 

Tabulation 을 사용하여 간단히 풀어지는 문제였다.

N = int(input())

dp = [0, 1, 1] + [0] * N

for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]
    
print(dp[N])