[python] Baekjoon 1003 : 피보나치 함수

문제 - Baekjoon 1003 : 피보나치 함수

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

1003번: 피보나치 함수

핵심

- 문제: N번째 피보나치 수를 구할 때, 0과 1이 각각 몇 번 출력되는지 계산하기

내용

- 이 문제는 피보나치 수열의 특정 항을 구하는 과정에서 0과 1이 출력되는 횟수를 계산하는 문제입니다. 피보나치 수열은 재귀적 방법으로 구현할 수 있지만, 이 경우 중복 계산이 많아 효율적이지 않습니다. 따라서 다이나믹 프로그래밍 기법을 사용하여 효율적으로 해결할 수 있습니다.

python display

접근 방법

1. 다이나믹 프로그래밍 사용: 각 피보나치 수에 대해 0과 1이 출력되는 횟수를 저장하는 배열을 만듭니다.
2. 초기 값 설정: 피보나치 수열의 첫 번째 항(0)과 두 번째 항(1)에 대해 0과 1이 출력되는 횟수를 초기화합니다.
3. 점화식 적용: 각 피보나치 수에 대한 0과 1의 출력 횟수는 이전 두 항의 0과 1의 출력 횟수의 합과 같습니다.
4. 결과 출력: 주어진 N에 대해 계산된 0과 1의 출력 횟수를 출력합니다.

코드

# 입력 처리
T = int(input())
for _ in range(T):
    N = int(input())

    # 0과 1 출력 횟수 배열 초기화
    zero_count = [1, 0] + [0] * (N - 1)
    one_count = [0, 1] + [0] * (N - 1)

    # 피보나치 수열 계산
    for i in range(2, N + 1):
        zero_count[i] = zero_count[i - 1] + zero_count[i - 2]
        one_count[i] = one_count[i - 1] + one_count[i - 2]

    print(zero_count[N], one_count[N])

 

풀이

- 0과 1이 출력되는 횟수를 각각 저장하는 배열을 초기화합니다.
- 피보나치 수열의 각 항에 대한 0과 1의 출력 횟수를 계산합니다.
- 배열에 저장된 값을 사용하여 각 N에 대한 0과 1의 출력 횟수를 출력합니다.

참고할 만한 자료

1. 다이나믹 프로그래밍: 반복되는 계산을 최소화하기 위한 프로그래밍 기법입니다.
2. 피보나치 수열: 각 항이 이전 두 항의 합으로 이루어지는 수열입니다.
3. Python 배열 사용법: Python에서 배열을 사용하는 방법과 예제입니다.

피보나치

 

추천 링크:
- 다이나믹 프로그래밍 설명: [GeeksforGeeks - Dynamic Programming](https://www.geeksforgeeks.org/dynamic-programming/))
- 피보나치 수열의 개념: [Khan Academy - Fibonacci sequence](https://www.khanacademy.org/math/algebra-home/alg-series-and-induction/alg-fibonacci-sequence))
- Python 배열 사용법: [W3Schools Python Arrays](https://www.w3schools.com/python/python_arrays.asp))