반응형
[문제 출처]
https://www.acmicpc.net/problem/9625
[문제 풀이]
버튼을 누르면 A는 B로 바뀌고, B는 BA로 바뀐다.
즉 k번째의 A와 B의 개수는 k-1번째의 A와 B의 개수에 따라 달라진다.
k-1번째에 A가 몇 개든지 모두 B로 바뀌기에 A의 개수는 k-1번째의 B의 개수에 따라 달라진다.
B의 개수만큼 A가 생기므로, k번째 A의 개수는 k-1번째의 B의 개수와 동일하다.
B의 개수는 A의 개수와 B의 개수 모두 중요한데,
k-1번째의 A가 모두 B로 바뀌고, k-1번째 B의 개수는 유지되므로 k번째 B의 개수는 k-1번째 A의 개수 + B의 개수가 된다.
#9625
k = int(input())
dp = [[1,0], [0,1]]
for i in range(2,k+1):
a = dp[i-1][1]
b = dp[i-1][0] + dp[i-1][1]
dp.append([a,b])
print(*dp[k])
반응형
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 1049 기타줄 (0) | 2023.01.05 |
---|---|
[python/파이썬] 백준 1026 보물 (0) | 2023.01.04 |
[python/파이썬] 백준 5622 다이얼 (0) | 2023.01.02 |
[python/파이썬] 백준 25304 영수증 (0) | 2022.12.29 |
[python/파이썬] 백준 2588 곱셈 (0) | 2022.12.29 |