문제

입출력

---

해설

처음에는 A로 시작하면서 A는 B로 변하고 B는 BA로 변한다는 문제이다.

1번 => B => 0 1
2번 => B A => 1 1
3번 => B A B => 1 2
4번 => B A B B A => 2 3
5번 => B A B B A B A B => 3 5
6번 누르면?
BA B BA BA B BA B BA => 5 8

감이 오는가..?

이건 피보나치다...

recursive하게 풀어서 해결해보자

코드

#입력
K = int(input())

#피보나치용 배열 만들기
fibo = [0]*(K+1)
fibo[1]=1

for k in range(2, K+1) :
    fibo[k] = fibo[k-1] + fibo[k-2]

print(fibo[K-1], fibo[K])

#다이나믹 프로그래밍