[python] 백준 9625번 - BABBA

초기에는 A가 표시 되어있고, 버튼을 누를 때마다 A->B, B->BA로 바뀐다.
버튼을 K번 눌렀을 때, A와 B의 개수를 구하는 문제이다.
 
 
다음과 같이 무작정 경우의 수를 적다보니 규칙을 발견할 수 있었다.

	A	B
기본값	1	0
1번 누름	0	1
2번 누름	1	1
3번 누름	1	2
4번 누름	2	3
5번 누름	3	5
6번 누름	5	8

A는 2번 누를 때 부터, B는 1번 누를 때 부터
피보나치 수열로 나타나는 것을 발견할 수 있었다.
그래서 n번째 피보나치 수를 구하는 함수를 재귀를 사용하여 푸는 것을 큰 틀로 잡았다.
 
첫 시도

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
        

K = int(input())
if K == 1:
    A = 0
    B = 1
else:
    A = fib(K - 1)
    B = fib(K)

print(A, B)

시간 초과로 인해 틀렸다.
 
피보나치 수열을 구하는 데 있어서, 재귀함수만 사용할 경우,
동일한 값을 여러 번 계산하게 되어 비효율적이다.
이를 해결하기 위해서는 DP의 풀이법 중 하나인 Memoization을 사용해야 함을 알게 되었다.

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    result = fib(n - 1) + fib(n - 2)
    memo[n] = result
    return result

K = int(input())
if K == 1:
    A = 0
    B = 1
else:
    A = fib(K - 1)
    B = fib(K)

print(A, B)

Memoization은 이미 계산된 값을 저장해 두고, 동일한 계산을 반복하지 않도록 하는 기법이다.
 
위 코드에선 memo라는 딕셔너리에 피보나치 수에 대한 계산 결과를 저장해서 사용하는 것이다.
fib 함수는 재귀적으로 피보나치 수를 계산하지만, 계산된 값이 이미 memo에 저장되어 있으면
이를 바로 반환하게 된다. 그렇지 않으면 memo에 새롭게 저장하는 방식이다.
이렇게 하면 동일한 값을 여러 번 계산하기 않게 되어 효율적이다.