💻 Problem
N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
💡 Approach
이 문제의 시간 제한은 0.25초이다.
1초가 약 1억이니 0.25초면 약 25,000,000이다.
피보나치의 기본 재귀 코드는 시간복잡도가 2^n이기에 재귀로 풀면 안 된다.
피보나치 수열은 n이 2 이상일 때, f(n) = f(n-1) + f(n-2) 이다.
재귀로 풀면 f(n)을 구할 때, f(n-1)을 구하기 위해 f(n-2)를 계산했음에도 f(n-2)를 다시 구해서 f(n-1)과 더해야 한다.

사진으로 보면 이해하기 더 쉽다.
위 사진에서 f(5)를 구하려고 할 때, 중복 계산이 여러 번 발생하는 것을 확인할 수 있다.
DP로 풀면 메모이제이션을 통해 중복 계산을 막으므로 시간이 훨씬 빠르다.
0부터 쭉 대입해 보면 점화식을 찾을 수 있다.
# 주어지는 것
f(0) -> [1, 0]
f(1) -> [0, 1]
# f(n) = f(n-1) + f(n-2) 식을 통해 구한 것
f(2) = f(1) + f(0) -> [1, 1]
f(3) = f(2) + f(1) -> [1, 2]
f(4) = f(3) + f(2) -> [2, 3]
f(5) = f(4) + f(3) -> [3, 5]
f(6) = f(5) + f(4) -> [5, 8]
...
배열 안에 있는 두 숫자는 순서대로 0이 출력되는 횟수, 1이 출력되는 횟수이다.
이렇게 대입해 보면 점화식을 찾을 수 있다.
점화식: dp[i] = [dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]]
점화식만 찾으면 코드 작성은 간단하다.
✏️ Solution
import sys
input = sys.stdin.readline
dp = [[]] * 41
dp[0] = [1, 0]
dp[1] = [0, 1]
for i in range(2, 41):
dp[i] = [dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]]
t = int(input())
for _ in range(t):
n = int(input())
print(*dp[n])
미리 계산해 둔 dp 테이블에서 조회하는 것을 테스트 케이스만큼 수행하므로 시간 복잡도는 O(t + n)이다.
여기서 n은 문제에서 주어진 대로 최대 40이다.
반응형
'Algorithm > 백준 (BOJ)' 카테고리의 다른 글
[Python] 백준/BOJ 1541번: 잃어버린 괄호 (Silver 2) (0) | 2025.01.22 |
---|---|
[Python] 백준/BOJ 9375번: 패션왕 신해빈 (Silver 3) (0) | 2025.01.21 |
[Python] 백준/BOJ 1874번: 스택 수열 (Silver 2) (0) | 2025.01.12 |
[Python] 백준/BOJ 3077번: 임진왜란 (Silver 3) (1) | 2025.01.11 |