백준 알고리즘 9625번 BABBA(python)

기본적인 다이나믹 프로그래밍 문제이다. 처음에 풀 때 dp에 문자열(EX: "BA")을 저장했는데

메모리 초과가 나와서 그냥 숫자로 해결했다.

k = int(input())
dp = [0]*(k+1)
dp[1] = 1
for i in range(2, k+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[k-1], dp[k])