[python/파이썬] 백준 9625 BABBA

[문제 출처]

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

9625번: BABBA

 

[문제 풀이]

버튼을 누르면 A는 B로 바뀌고, B는 BA로 바뀐다.

즉 k번째의 A와 B의 개수는 k-1번째의 A와 B의 개수에 따라 달라진다.

 

k-1번째에 A가 몇 개든지 모두 B로 바뀌기에 A의 개수는 k-1번째의 B의 개수에 따라 달라진다.

B의 개수만큼 A가 생기므로, k번째 A의 개수는 k-1번째의 B의 개수와 동일하다.

 

B의 개수는 A의 개수와 B의 개수 모두 중요한데, 

k-1번째의 A가 모두 B로 바뀌고, k-1번째 B의 개수는 유지되므로 k번째 B의 개수는 k-1번째 A의 개수 + B의 개수가 된다.

 

#9625

k = int(input())

dp = [[1,0], [0,1]]

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

  dp.append([a,b])

print(*dp[k])