버튼을 누를 때마다 변화 과정을 표로 그려봤더니 규칙성을 확인할 수 있었다. 규칙성이 성립되기에 점화식을 세울 수 있었다.
K | A | B | 실행결과 |
---|---|---|---|
1 | 0 | 1 | B |
2 | 1 | 1 | BA |
3 | 1 | 2 | BAB |
4 | 2 | 3 | BABBA |
5 | 3 | 5 | BABBABAB |
A의 i번째 항과 A의 (i+1)번째 항을 더하면 A의 (i+2)번째 항이 나온다. B역시 A와 동일한 규칙성을 가진다.
K = int(input())
A = [0] * 46
A[0] = 1
A[1] = 0
B = [0] * 46
B[0] = 0
B[1] = 1
for i in range(2, K+1):
A[i] = A[i-2] + A[i-1]
B[i] = B[i-2] + B[i-1]
print(A[K], B[K])