[baekjoon] 백준 9625번(파이썬): BABBA

문제

9625번: BABBA

알고리즘

- 반복문을 통해 점화식을 수행한다.

- A의 개수는 이전 화면에 B의 개수

- B의 개수는 이전 화면에 A의 개수와 B의 개수

index	화면	A의 개수	B의 개수
1	B	0	1
2	BA	1	1
3	BAB	1	2
4	BABBA	2	3
5	BABBABAB	3	5
6	BABBABABBABBA	5	8
7	BABBABABBABBABABBABAB	8	13

코드

import sys

k = int(sys.stdin.readline())
dp = [[0 for _ in range(2)] for _ in range(46)]
dp[1][0] = 0
dp[1][1] = 1

# A : 이전 화면에 B의 개수
# B : 이전 화면에 A와 B의 개수
# f(a) = f(b - 1)
# f(b) = f(a - 1) + f(b - 1)
# 반복문을 통해 점화식을 수행
for i in range(2, k + 1):
    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])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법