백준-1003-피보나치 함수

1. 문제 출처

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

1003번: 피보나치 함수

2. 풀이

Dynamic Programming botton up 방법을 사용하여 입력 받은 값 중 최대값의 0,1의 개수를 구하면 그 밑의 값은 dp배열에 저장되어 있다. 그것을 이용하여 풀면 다음과 같은 코드가 나온다.

## 입력 받는 부분
import sys
t = int(sys.stdin.readline())
input_list = []
for i in range(t):
    input_list.append(int(sys.stdin.readline()))
    

## 입력받은 값중 최대의 값
max_test_case = max(input_list)

##  botton up에서 사용할 배열
dp = [[0 , 0] for _ in range(max_test_case+2)]

## 반복문을 사용하기 위해 0과 1은 미리 정해놓는다.
dp[0] = [1,0]
dp[1] = [0,1]

## dp[i] 는 dp[i-2], dp[i-1] 의 0,1 개수의 합과 같다. 
for i in range(2,max_test_case+1):
    dp[i] = [dp[i-2][0]+dp[i-1][0] , dp[i-2][1] + dp[i-1][1]]

## 입력받은 값에 따라 0,1 개수를 출력해준다. 
for input_num in input_list:
    print(dp[input_num][0],dp[input_num][1] )