[백준] 1003번 피보나치 함수, 파이썬 문제 풀이

문제

백준 1003번 피보나치 함수를 진행했을 때 0, 1이 몇 번 출력되는지 세는 문제를 해결했습니다.

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

1003번: 피보나치 함수

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

문제 풀이

피보나치 수열이 문제에 주어져 있고, 0과 1이 몇 번 출력되는지 세는 문제입니다. 처음엔 큰 생각 없이 전역 변수를 선언해 실제 피보나치 함수를 진행해서 카운트하는 방식으로 문제를 해결하려고 했습니다. 시간 제한이 0.25초이지만, N이 40까지라서 이 정도는 괜찮지 않을까..? 하는 안일한 마음으로 접근했습니다.

피보나치 함수를 실행해서 직접 카운트하는 코드는 다음과 같습니다.

def fibonacci(n):
    global countZero
    global countOne
    if (n == 0):
        countZero+=1
        return 0
    elif (n == 1):
        countOne+=1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

TC = int(input())

for _ in range(TC):
    countZero=0
    countOne=0
    N = int(input())
    fibonacci(N)
    print(countZero, countOne)

결과는 당연히 시간 초과입니다. 시간을 줄이기 위해서 어떻게 해야할지 고민을 했습니다. 당연히 피보나치 함수를 직접 돌면 안될 것 같다는 느낌이 들었습니다. 피보나치 수열은 f(n) = f(n-1) + f(n-2) 라는 점화식이 존재합니다. 이렇게 점화식이 대놓고 나왔는데 DP를 쓰지 않을 이유가 없습니다. 그래도 혹시 모르니 몇 개 나열해봤습니다.

N	0이 출력되는 횟수	1이 출력되는 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13

규칙이 보이시나요? N-1, N-2번째를 더하면 N번째 값이 나오는 것을 볼 수 있습니다.

0과 1이 출력되는 횟수를 리스트 형식으로 DP에 저장한다면 다음과 같은 점화식이 나올 수 있습니다.

 

DP[N] = [ DP[N-1][0]+DP[N-2][0], DP[N-1][1]+DP[N-2][1] ]

 

이를 활용해 코드로 작성하면 다음과 같습니다.

TC = int(input())

for _ in range(TC):
    N = int(input())

    DP = [[]]*41
    DP[0] = [1,0]
    DP[1] = [0,1]
    DP[2] = [1,1]

    for i in range(3, N+1):
        DP[i] = [DP[i-1][0]+DP[i-2][0],DP[i-1][1]+DP[i-2][1]]

    print(DP[N][0], DP[N][1])

 

정리

피보나치 함수가 주어졌지만, DP로 문제를 해결할 수 있었습니다. 이전 값을 활용해 값을 도출해내므로 시간이 많이 단축되는 것을 확인할 수 있었습니다.