[백준/Python] 2193번: 이친수

문제

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

2193번: 이친수

---

문제 요약

0과 1로만 이루어진 수를 이진수라고 한다.

 

이친수는 이진수들 중 특별한 성질을 갖는 수이다.

 

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. (11을 부분 문자열로 갖지 않는다.)

 

n이 주어졌을 때, n자리 이친수의 개수를 출력한다.

---

코드

n = int(input())

dp = [0, 0] * 91
# dp[i][0]는 i자리 이친수 중 마지막 수가 0인 수의 개수
# dp[i][1]는 i자리 이친수 중 마지막 수가 1인 수의 개수

dp[1] = [0, 1]

for i in range(2, 91):
    dp[i] = [dp[i-1][0] + dp[i-1][1], dp[i-1][0]]

print(sum(dp[n]))

---

코드 설명

1. i자리 이친수의 개수 정보를 저장하는 메모이제이션 테이블 dp를 생성한다.

+ dp[i][0]는 i자리 이친수 중 마지막 수가 0인 수의 개수, dp[i][1]는 i자리 이친수 중 마지막 수가 1인 수의 개수를 갖는다.

 

2 - 1. i자리 이친수 중 마지막 수가 0인 수 뒤에 1또는 0을 붙여 i+1자리 이친수를 만들 수 있다.

 

2 - 2. i자리 이친수 중 마지막 수가 1인 수 뒤에 0을 붙여 i+1자리 이친수를 만들 수 있다. 

+ 뒤에 1을 붙이면 조건 2를 만족하지 않는다.

 

3. Bottom - up 방식으로 dp[1]부터 dp[90]까지 작성한다.

 

4. dp[n][0] + dp[n][1]을 출력한다.