다이나믹 프로그래밍 - 백준 2193 [Python]

Problem)

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

2193번: 이친수

Solution)

D[i][j] = i 자리 이친수의 개수 중에서 j로 끝나는 것의 개수 (j=0,1)

 

가능한 경우는

• 0으로 끝나는 경우 (D[i][j])
  • 앞에 0과 1이 올 수 있다.
  • D[i-1][0] + D[i-1][1]
• 1로 끝나는 경우 (D[i][1])
  • 앞에 1은 올 수 없다. 즉, 0만 올 수 있다.
  • D[i-1][0]

 

Answer)

n = int(input())
d = [[0]*3 for _ in range(91)]
d[1][1] = 1
d[1][0] = 0

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]))