-
9625. [Python]BABBAPython_알고리즘/Silver V 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. 문제를 푸는데 도움이 되는 지식
- 다이나믹 프로그래밍
'Python_알고리즘 > Silver V' 카테고리의 다른 글
1769. [Python]3의 배수 (0) 2023.04.26 2822. [Python]점수 계산 (0) 2023.04.08 8979. [Python]올림픽 (0) 2023.04.04 2740. [Python]행렬 곱셈 (0) 2023.03.31 2535. [Python]아시아 정보올림피아드 (0) 2023.03.29