[Python Algorithm] 피보나치 함수 BOJ #1003

문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

내 문제 풀이

t = int(input())
nums = []
for i in range(t): nums.append(int(input()))

memory = []
for i in range(max(nums)+1):
    if i == 0: memory.append([1, 0])
    elif i == 1: memory.append([0, 1])
    else: memory.append([memory[i-1][0]+memory[i-2][0], memory[i-1][1]+memory[i-2][1]])

for i in nums: print(" ".join(list(map(lambda x: str(x), memory[i]))))

👉 DP 문제로, 일정한 규칙을 찾고 메모지에이션 방식을 사용하여 연산해주는게 포인트!

실제 피보나치 연산을 하는 재귀함수를 만들어서 0, 1의 호출을 카운트하면 시간초과가 남

따라서 0, 1의 호출 횟수를 구할 수 있는 점화식을 찾아야 한다.

 

[점화식]

• fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 호출
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)을 호출
  n이 0이면 [0이 한 번, 1이 0번] 출력되고 n이 1이면 [0이 0번, 1이 1번] 출력되는데
  n이 2면 결국 fibonacci(1)과 fibonacci(0)의 결과를 합한 [0이 한 번, 1이 한 번] 출력됨

따라서 [0이 출력된 횟수, 1이 출력된 횟수]를 보면

n이 0일 경우 [1, 0], n이 1일 경우 [0, 1] => n이 2일 경우 [1+0, 0+1]가 된다.

=> memory[n] = [(memory[n-1][0] + memory[n-2][0]), (memory[n-1][1] + memory[n-2][1])]

 

[풀이 설명]

• 문제의 입력을 모두 받아놓고, 그 중 가장 큰 수까지 0, 1의 출력 횟수를 구해서 memory에 저장했다.
• memory[0], [1]의 경우에는 연산이 불가하므로 따로 조건을 설정하여 알맞은 답을 넣어준다.
• 그 외의 경우에는 memory에 위에서 구한 점화식의 결과에 해당하는 값을 넣어주었다.

 

💡 피드백

• 처음에 점화식을 도출하는데에 시간이 좀 걸렸는데,
  이런 문제들은 누적하는 값을 이용하는 경우가 많다는걸 기억하고 있어야겠다.