728x90
[파이썬] 백준 9625 : BABBA
https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
실버 5
구현, DP
접근
A는 B로, B는 BA로 바꾸는 걸 반복하고, A와 B의 개수를 세어 보았다.
A (1, 0)
B (0, 1)
BA (1, 1)
BA B (1, 2)
BA B BA (2, 3)
BA B BA BA B (3, 5)
BA B BA BA B BA B BA (5, 8)
버튼을 처음 누른 뒤의 화면이 B이므로 B가 된 이후부터의 A의 개수는
0, 1, 1, 2, 3, 5 ...
B의 개수는
1, 1, 2, 3, 5, 8....
엥? 이거 완전 피보나치 수열 아니냐?
코드
import sys
K = int(sys.stdin.readline())
prime = [0]*(K+1)
prime[1] = 1
for i in range(2, K+1):
prime[i] = prime[i-1] + prime[i-2]
print(prime[K-1], prime[K])728x90
'알고리즘 문제 풀이' 카테고리의 다른 글
| [파이썬] 백준 1003 : 피보나치 함수 (0) | 2022.03.12 |
|---|---|
| [파이썬] 백준 13301 : 타일 장식물 (0) | 2022.03.12 |
| [파이썬] 백준 15312 : 이름 궁합 (0) | 2022.03.11 |
| [파이썬] 백준 17202 : 핸드폰 번호 궁합 (0) | 2022.03.10 |
| [파이썬] 백준 9655 : 돌 게임 (0) | 2022.03.09 |