[백준][9625번] BABBA

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

 

 

 

 

 

내 생각

• 1번 누를 때: A → B  : A 1개, B 1개
• 2번 누를 때: B → BA  : A 1개, B 2개
• 3번 누를 때: BA → BAB  : A 2개, B 3개
• 4번 누를 때: BAB → BABBA  : A 3개, B 5개
• 5번 누를 때: BABBA → BABBABAB  : A 5개, B 8개

→ 피보나치 수열인 것을 확인할 수 있다 !

A는 K-1번 째, B는 K번 째 값 !

 

 

 

내 코드

K = int(input())

fib = [0] * (K + 1)
fib[1] = 1

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

A_count = fib[K - 1]
B_count = fib[K]

print(A_count, B_count)