[백준/python] 9625번: BABBA

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

알고리즘 분류

- 다이나믹 프로그래밍

코드

K = int(input())
dp = [[0 for _ in range(2)] for _ in range(K+1)]

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

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

print(dp[K][0], dp[K][1])

풀이

직접 써서 계산해보면

1번째: b

2번째: ba

3번째: bab => ba + b

4번째: babba => bab + ba

로 n-1번째와 n-2번째를 더한 것이 n번째임을 알 수 있다

때문에 b와 a의 개수도 n-1번째와 n-2번째를 더한 것이 된다

점화식: F(n) = F(n-1) + F(n-2)