-
1003. [Python]피보나치 함수Python_알고리즘/Silver III 2023. 5. 19. 22:51
1. 문제
https://www.acmicpc.net/problem/1003
2. 접근 방법
- 시간 제한: 0.25초
- 메모리 제한: 128MB
- 구현
3. 파이썬 코드
def fibonacci(): # 피보나치 함수에서 각각 0과 1이 나오는 횟수 num_list = [[1,0],[0,1]] # 최대 40 까지 오기 때문에 미리 리스트를 생성해둔다. for i in range(2,41): num_list.append([num_list[i-1][0]+num_list[i-2][0],num_list[i-1][1]+num_list[i-2][1]]) return num_list T = int(input()) # 피보나치 수열 함수 생성 fibo = fibonacci() for _ in range(T): # 미리 생성해둔 함수에서 인풋값에 따라 num = int(input()) print(*fibo[num])
4. 문제를 풀고난 후 생각
- 다이나믹 프로그래밍을 접하면 제일 기본적으로 들어보는 피보나치 함수를 약간 변형한 문제이다.
- 기존의 DP로 피보나치를 구현하는 것과는 좀 다르게 0의 갯수와 1의 갯수를 각 숫자별로 카운트 해주고 피보나치 함수를 구하는 것처럼 각 인덱스 에서의 0과 1의 갯수를 더해주는 방식으로 문제를 해결 하였다.
=> 기존의 피보나치 함수의 경우 0 1 1 2 3 5 ... 이런 식으로 진행되지만 구현한 코드의 경우는
=> [1,0] [0,1] [1,1] [1,2] [2,3] ... 이런 식으로 각 인덱스별 0과 1의 갯수를 더해주는 방식으로 구현하여 해결하였다.
5. 문제를 푸는데 도움이 되는 지식
- 다이나믹 프로그래밍
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1935. [Python]후위 표기식2 (0) 2023.05.23 10974. [Python]모든 순열 (0) 2023.05.21 1431. [Python]시리얼 번호 (0) 2023.04.23 1213. [Python]팰린드롬 만들기 (0) 2023.04.22 1788. [Python]피보나치 수의 확장 (0) 2023.04.19