[python] 백준 9625 BABBA

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

9625번: BABBA

 

문제 해결

• A→B, B→BA로 바뀌고 k번째 바뀌었을 때 A, B의 개수를 구하는 것이므로 DP를 이용하는 것이 편할 것이란 생각이 든다.
• dp[i][0]는 i번 눌렀을 때 A의 개수, dp[i][1]은 i번 눌렀을 때 B의 개수로 정의한다.
• dp[0][0] = 1, dp[0][1] =0 에서 시작
• dp[i][0] = dp[i-1][1] 이고 dp[i][1] = dp[i-1][0] + dp[i-1][1] 임을 알 수 있다.

 

CODE

import sys
input = sys.stdin.readline

k = int(input())
dp = [[0,0] for _ in range(k+1)] # A, B 개수
dp[0][0] = 1
for i in range(1,k+1): # 'A', B'
    dp[i][0] = dp[i-1][1]
    dp[i][1] = dp[i-1][0] + dp[i-1][1]
print(dp[k][0], dp[k][1])