Python_알고리즘/Silver V
9625. [Python]BABBA
최근영
2023. 4. 5. 15:34
1. 문제
https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 다이나믹 프로그래
3. 파이썬 코드
def dp():
# 정답 리스트
ans_list = [[1,0]]
# K가 45까지 들어오기때문에
for _ in range(45):
ans_list.append([ans_list[-1][1],ans_list[-1][0]+ans_list[-1][1]])
return ans_list
K = int(input())
ans = dp()
# 들어온 K의 값 출력
print(*ans[K])
4. 문제를 풀고난 후 생각
- 코드를 짜기보다는 문제의 규칙이 어떠한 규칙으로 이루어 지는지를 파악했다.
- A의 갯수와 B의 갯수가 어떻게 결정되는지 찾는 것이 중요했고, A의 갯수는 이전의 B의 갯수가 그대로 A의 갯수가 되었으며 B의 갯수는 이전의 A와 B의 갯수의 합이 B의 갯수가 되는 것을 파악했다.
- 이 규칙을 찾고난 후 코드를 짜는 것은 어렵지 않았다.
- 초기 값으로 A와 B의 갯수를 선언해 줬고, K값이 45까지 결정되어있으므로 45까지 반복문을 통해서 리스트의 값을 추가해 나가는 방식으로 구현했다.
- A는 이전 리스트 B의 갯수를 넣었고, B는 이전 리스트 A,B의 합을 넣어주는 식으로 만들었다.
5. 문제를 푸는데 도움이 되는 지식
- 다이나믹 프로그래밍