[백준]2193 이친수 파이썬 python

문제링크

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

2193번: 이친수

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
d = [[0]*2 for _ in range(91)]
d[1] = [0,1]
 
for i in range(2,n+1):
    d[i][0] = d[i-1][0]+d[i-1][1]
    d[i][1] = d[i-1][0]
 
print(sum(d[n]))

 

POINT

- DP로 접근

- 풀이 방법:

1이 두번 연속 나타나지 않기 위해서 마지막 수를 저장하는 전략을 채택한다.

'd[i][j] = 총 길이가 i이고, 마지막 수가 j인 이친수 갯수' 라고 정의한다.

1을 추가하려면 1이 연속되지 않기 위해서, 직전 수가 0인 경우에만 1을 추가할 수 있다. ==> d[i][1] = d[i-1][0]

0을 추가하려면 직전 수가 0이든 1이든 상관없이 가능하다. ==> d[i][0] = d[i-1][0]+d[i-1][1]