[백준 2193 : PYTHON] 이친수

문제 풀기 : 2193번

2193번: 이친수

문제

이친수는

   1. 0과 1로만 이루어진 수

   2. 0으로 시작하지 않는다.

   3. 1이 두 번 연속으로 나타나지 않는다.

 

N(1 ≤ N ≤ 90)

 

N자리 이친수의 개수를 구하라.

 

문제풀이

n = 5 까지의 케이스를 찾아본다.

 

n = 4(하늘색 표시) 부터 살펴보면 n = 2와 n =3의 경우의 수가 다 들어가 있는 것을 볼 수 있다. → 10, 00, 01

n = 5(빨간색 표시) 부터 살펴보면 n = 3와 n =4의 경우의 수가 다 들어가 있는 것을 볼 수 있다. → 100, 101, 010, 000, 001

그러므로 점화식은 dp[i] = dp[i-1] + dp[i-2] 이 된다.

 

* dp는 최적의 경우의 수를 저장하는 테이블이다.

 

전체코드

import sys
input = sys.stdin.readline

n = int(input())

# n 자리 수 만큼 dp 테이블 생성 => n+1
dp = [0] * (n + 1)
dp[1] = 1

# dp 점화식
# 경우의 수를 따져보면 피보나치 수열과 비슷한 형태를 띄고 있음
for i in range(2, n+1):
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n])