[백준]피보나치 함수

문제

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

풀이

기존 피보나치 함수를 응용한 문제로 DP를 활용하면 쉽게 풀 수 있다.

• 기본 피보나치 문제를 풀면서 0과 1이 몇 번 사용되는지 개수를 세어야 한다.
• 처음에는 DP를 사용하지 않고 재귀로 풀었다. n이 0과 1이면 return하면서 수를 세었지만, 바로 시간초과가 떴다.
• 두 번째로, DP 하향식으로 풀려 했지만 전역변수가 사용되고 코드가 더러워져 DP 상향식을 사용하기로 했다.
• 0부터 n까지 피보나치 함수값을 구하면서 동시에 0과 1을 해당 n에서 얼마나 사용했는지 구한 뒤, 이후에 재사용하는 방법을 사용했다.

코드

# 입력 값 정리
import sys
T = int(sys.stdin.readline())
test_case = []
for _ in range(T):
  test_case.append(int(sys.stdin.readline()))

# 테스트 케이스별 값 구하기
for t in test_case:
	# 0과 1이면 계산 없이 주어진 값 출력
  if t == 0:
    print(1, 0)
  elif t == 1:
    print(0, 1)
   # 그 이외에는 DP 상향식에다가 0과 1 사용량 저장 리스트를 따로 계산
  else:
    num = t + 1
    dp = [0] * num
    count_dp = [[0,0] for _ in range(num)]
    dp[0] = 0
    dp[1] = 1
    count_dp[0] = [1,0]  
    count_dp[1] = [0,1]
    for i in range(2,num):
      dp[i] = dp[i-1] + dp[i-2]
      count_dp[i] = [x+y for x,y in zip(count_dp[i-1], count_dp[i-2])] 
    zero, one = count_dp[t]
    print(zero, one)