백준 9625 BABBA / python

문제 : 9625

풀이 point

패턴을 구해보면 쉽게 알 수 있다. A는 B로 바뀌고 B는 BA로 바뀐다. 그러니 A는 버튼을 누르기전 B의 개수만큼 존재할 수 있고, B는 버튼을 누르기 전 A의 개수와 B의 개수만큼 존재할 수 있다.

풀이 방법

패턴을 찾았다며 쉽게 코드를 짤 수 있다.

코드

#백준 9625, BABBA

K = int(input())

'''
1 0
0 1
1 2
2 3
3 5
5 8

BABBABAB
BABBABABBABBA

'''

A = [1, 0, 1]
B = [0, 1, 1]

for i in range(3, K+1):
    A.append(B[i-1])
    B.append(A[i-1] + B[i-1])

print(A[K], B[K])