백준 #9625 BABBA 파이썬
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
<내 풀이>
1. 입력
입력 값 k를 정수형으로 입력 받는다.
2. 초깃값 설정 부분
처음 기계를 발견했을 때, 화면에는 A만 표시되어 있는 상태를 표현한다.
A의 개수를 저장하는 a 리스트에 1 , B의 개수를 저장하는 b 리스트에 0을 넣는다.
(0번째 시행했을 때 A가 1개, B가 0개 있다는 뜻)
3. for 문 부분--
계산한 A개수와 B개수를 계속 리스트에 넣는 다이나믹 프로그래밍
구해야 하는 것은 버튼을 K번 눌렀을 때, 화면에 표시되는 A와 B의 개수인데,
버튼을 한 번 누를 때마다 B는 BA로 바뀌고, A는 B로 바뀐다고 하였다.
b는 버튼을 한 번 누를 때마다 a가 b 개 늘어나게 만들고, b의 개수에는 영향을 주지 않는다.
----> 버튼을 한 번 누른 후 a의 개수는 버튼을 누르기 이전 b의 개수와 같다.
a는 버튼을 한 번 누를 때마다 원래 있는 a가 모두 사라지게 만들고, b가 a개 늘어나게 만든다.
---->버튼을 한 번 누른 후 b의 개수는 버튼을 누르기 이전 b의 개수 + 버튼을 누르기 이전 a의 개수와 같다.
for i in range(1,k+1):
버튼을 1번 부터 k번까지 누르는 동안
(*여기서 i는 지금까지 버튼을 누른 횟수와 같다)
a.append(b[i-1])
a 리스트에 'i-1번 버튼을 눌렀을 때 B의 개수'를 append 한다
b.append(b[i-1]+a[i-1])
b 리스트에 'i-1번 버튼을 눌렀을 때 B의 개수 + i-1번 버튼을 눌렀을 때 a의 개수'를 append 한다.
4. 출력
k번 버튼을 누르는 for문이 끝난 뒤,
a리스트의 마지막 원소(a[-1])와 b리스트의 마지막 원소(b[-1])를 한 줄로 출력한다.
<풀이 후>
다른 사람들의 코드를 보니 이것도 피보나치 수열이라고 함. 몰랐다. 그리고
a, b = b , b+a
이렇게 a(A의 개수)랑 b(B의 개수)를 간단히 재정의 하면서 for문을 돌리면
굳이 리스트에 새로운 수를 계속 추가하지 않아도 되는 문제였다!