[BOJ][Python] 1003 피보나치 함수

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 3
• 문제 유형: DP
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

 

---

[문제]

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

 

[배운 점]

처음에 재귀함수로 구현할 때, 배열 대신 정수로 카운트를 셌다. (zcnt += 1, ocnt += 1) -> 에러 발생

def f(n, zcnt, ocnt):
    if n == 0:
        zcnt += 1  # 이 값은 함수 안에서만 증가하고 외부에서는 반영되지 않음
        return 0
    elif n == 1:
        ocnt += 1  # 이 값도 마찬가지로 외부에 반영되지 않음
        return 1
    else:
        return f(n-1, zcnt, ocnt) + f(n-2, zcnt, ocnt)

zero, one = 0, 0
f(5, zero, one)
print(zero, one)  # zero와 one은 여전히 0으로 출력됨

 

파이썬에서 정수형(int)는 불변 객체(immutable)이므로, 함수 외부에는 반영되지 않는다. 

* 불변 객체란 값을 변경할 수 없는 객체 

 

가변 객체인 리스트(배열)을 사용하면 함수 내에서 값을 수정하고, 그 변경된 값을 함수 외부에도 유지할 수 있다. 

 

 

[코드]

1. 재귀함수로 구현 - 시간초과

def f(n, zcnt, ocnt):
    if n == 0:
        zcnt[0] += 1
        return 0
    elif n == 1:
        ocnt[0] += 1
        return 1
    else:
        return f(n-1, zcnt, ocnt) + f(n-2, zcnt, ocnt)

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

    zero = [0]
    one = [0]
    f(n, zero, one)

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

 

2. DP로 구현 

- 기본 피보나치 구현을 하듯이 하되, 초기 숫자를 0의 갯수, 1의 갯수를 저장해줄 DP를 따로 만든다. 

T = int(input()) 

def fcnt(n):
    dp_zero = [0] * (n + 1)  # f(0)의 호출 횟수
    dp_one = [0] * (n + 1)   # f(1)의 호출 횟수

    if n >= 0:
        dp_zero[0] = 1  # f(0)이 호출되는 경우
    if n >= 1:
        dp_one[1] = 1   # f(1)이 호출되는 경우

    for i in range(2, n + 1):
        dp_zero[i] = dp_zero[i-1] + dp_zero[i-2]
        dp_one[i] = dp_one[i-1] + dp_one[i-2]

    return dp_zero[n], dp_one[n]

for _ in range(T):
    n = int(input())
    zero_count, one_count = fcnt(n)
    print(zero_count, one_count)