65. Python 백준 1003 번 피보나치 함수 자세한 설명

안녕하세요 코딩하는 덕구입니다.

Python 백준 1003 번 피보나치 함수입니다.

다이나믹 알고리즘 문제입니다.

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

1003번: 피보나치 함수

 

 

input N이 주어졌을 때 0, 1이 출력되는 횟수를 구해서 출력하는 문제입니다.

기본적인 전제입니다.

fibonacci(0)은 0을 출력하게 됩니다. (문제에 주어진 코드의 구현상)

fibonacci(1)은 1을 출력하게 됩니다. (문제에 주어진 코드의 구현상)

 

N이 2일 때 ( fibonacci(2)는 )

fibonacci(1),  fibonacci(2)를 호출하게 되고 

fibonacci(1)의 출력 1, fibonacci(0)의 출력 0

즉 fibonacci(2)는 1을 1번 출력하고, 0을 1번 출력하게 됩니다.

 

그럼 fibonacci(3)은 어떻게 될까요?

fibonacci(3) = fibonacci(2) + fibonaci(1) 

fibonacci(2)는 방금 구했죠, 1을 1번 0을 1번

fibonacci(1)은 문제에 주어졌습니다. 1을 1번 0을 0번

fibonacci(3) 은 1을 2번, 0을 1번

즉 fibonacci(3)의 1과 0이 등장한 횟수는

fibonacci(2)에서 등장한 1과 0의 횟수 +  fibonacci(1)에서 등장한 1과 0의 횟수라는 것을

알 수 있습니다.

위와 같은 방법으로 접근하여 코드를 구현해 봅시다.

 

각 index별 0이 등장한 횟수, 1이 등장한 횟수를 담는 리스트를 선언합니다.

# (0이 출력된 나온 횟수, 1이 출력된 횟수)
list = [[1, 0], [0, 1]]

 

input N의 0과 1이 등장한 횟수가 리스트에 있는지 체크를 하고

만약 있다면 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.

if N <= len(list)-1:
    print(list[N][0], list[N][1])

 

없다면 없는 숫자부터 N까지

0이 등장한 횟수, 1이 등장한 횟수를 구해서 차례대로 채우고 난 후

input N의 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.

else:
    for i in range(len(list), N+1):
        zero = list[i - 1][0] + list[i - 2][0]
        one = list[i - 1][1] + list[i - 2][1]
        list.append([zero, one])
    print(list[N][0], list[N][1])

 

Python 백준 1003 번 최종 코드입니다.

# (0이 출력된 나온 횟수, 1이 출력된 횟수)
list = [[1, 0], [0, 1]]
T = int(input())
for t in range(T):
    N = int(input())
    if N <= len(list)-1:
        print(list[N][0], list[N][1])
    else:
        for i in range(len(list), N+1):
            zero = list[i - 1][0] + list[i - 2][0]
            one = list[i - 1][1] + list[i - 2][1]
            list.append([zero, one])
        print(list[N][0], list[N][1])

 

 

Python 백준 1003 번 피보나치 함수이었습니다. 감사합니다.