BOJ 9625 - BABBA

문제

백준 온라인 저지 - 9625번

풀이 과정

동적 계획법 을 활용한 문제입니다.
각 문자가 일정 규칙으로 변환되는데 이를 활용해서 점화식을 세우면 됩니다.

저 같은 경우 문장의 길이가 피보나치 수열을 따르면서 B 의 개수도
피보나치 수열의 개수대로 증가된다는 것을 이용해서 문제를 풀었는데
다른 분들의 풀이를 보니 그냥 A 와 B 각각에 대해서 점화식을 세우고 순회를 하면 간단하게 해결할 수 있었습니다.

K 가 작기 때문에 완전 탐색 으로 구현해도 풀 수 있을 것 같기는 한데
이후에 비슷한 유형에 대비해서 접근 방법을 기억해놔야 할 것 같습니다.

코드

K = int(input())


def solution():
    dp = [-1] * (K + 1)
    dp[0], dp[1] = 1, 1

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

    if K == 1:
        return "0 1"
    else:
        return f"{dp[K] - dp[K - 1]} {dp[K - 1]}"


print(solution())