[백준]1003번 피보나치 함수 - DP

 

n = int(input())

for i in range(n):
    case = int(input())

    zero = [1, 0, 1]
    one = [0, 1, 1]

    if case >= 3 :
        for i in range(3, case+1):
            zero.append(zero[i-2]+zero[i-1])
            one.append(one[i-2]+one[i-1])

    print(zero[case], one[case])

 

코드 설명

기본적으로 피보나치 수의 3번째 까지는 0과 1이 등장한 횟수로 초기화하여 준다.

3이상의 숫자가 나올 경우 피보나치의 점화식을 이용하여 zero, one 리스트에 값을 추가하여 준다.

 

Point : DP 이론을 통하여 빠른 시간내에 구할 수 있는 문제이다. 값을 기억하면서 다음 계산에 이용하는 방식이다.

일단 3번째의 수 까지는 초기화를 통해 default 로 정해두고, 그 이상의 수가 나올 경우 피보나치 수열의 점화식 i-2 + i-1 을 이용하여 0과 1각 리스트를 따로 덧셈을 진행한다. 

이렇게 하면 0과 1이 출력되는 횟수는 누적이 되며 정답을 구할 수 있다.