[백준 9625] BABBA (Python)

9625번: BABBA

n = int(input())

d = [[] for _ in range(n+1)]
d[0] = [1, 0]
d[1] = [0, 1]

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

print(d[n][0], end=' ')
print(d[n][1])

 며칠 전 펜과 노트를 안 가지고 있어서 머리로 한참 고민하다가 나중에 펜이랑 노트 가져와서 다시 풀고자 마음먹은 문제였다. 식을 써보니 너무나도 쉬운 점화식으로 이루어진 것을 확인할 수 있었고, 덕분에 수월하게 해결했다. 

 이전에 배웠던 것과 같이 점화식을 세우는 게 가장 중요한 DP였다. $ A_i = A_{i-1} + A_{i-2} $, 리스트의 형태만 띠었을 뿐 피보나치와 같은 원리의 문제!