[백준 1003] 피보나치 함수 (python)

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

1003번: 피보나치 함수

피보나치 함수 문제

피보나치 수열에서 원하는 수를 호출 했을 때, 0과 1이 총 몇번 호출되는지 세어보는문제

피보나치에 대한 개념을 잘 이해하고 있다면 간단하게 접근 할 수 있는 문제였다.

내가 푼 정답코드

T = int(input())
for _ in range(T):
    N = int(input())
    a, b = 1, 0 # 0과 1이 호출된 횟수
    for i in range(N):
        # 0은 1이 호출된 횟수만큼, 1은 0과 1이 호출된 합만큼 출력됨
        a,b = b, a+b 
    print(a,b)

전형적인 D.P 문제였다. 일반적인 피보나치 함수를 구현하는 거처럼 재귀를 이용하여 풀 경우 무조건 시간 초과가 난다 (제한 시간 0.25초)

피보나치 수열은 DP로 구현해보면서 개념을 잡는 기초 문제로 자주 나오는 예시이다.

다만,  이 문제의 경우 굳이 피보나치 수열을 구현할 필요가 없는 문제이다. 문제의 주어진 조건인 0과 1의 호출된 횟수를 세는 문제이다. 일반적인 피보나치 수열에 대해서 생각해보면 쉽게 답을 찾을 수 있다.

피보나치 수열은 f(n) = f(n-1) + f(n-2)의 형태로 이루어져있다.

n = 2일때 부터 생각해보면 각각 0과 1의 호출 횟수는 1 / 1

n = 3일때 f(3) = f(2) + f(1) → 각각 1 / 2

n = 4일때 f(4) = f(3) + f(2) → n이 3일때와 2일때의 더한 합인 2 / 3

n = 5일때 f(5) = f(4) + f(3) → n이 4일때와 3일때의 더한 합인 3 / 5

n= 6 일때 f(6) = f(5) + f(4) → n이 5일때와 4일때의 더한 합인 5 / 8

반응형

....

n = N일때 f(N) = f(N-1) + f(N-2) → n이 N-1일때와 N-2일때의 더한 합 

의 형태로 이루어지는 것을 알 수 있다.

즉 n일때 0의 호출은 n-1의 1의 호출과 동일함을 볼 수 있고 1의 호출은 n-1의 0과 1의 호출의 합임을 알 수 있다.

요약하면 0의 호출은 0부터 시작하는 피보나치 수열이고 1의 호출은 1부터 시작하는 피보나치 수열이란 것을 알면 쉽게 해결 할 수 있는 문제이다.

---

느낀 점

피보나치 수열을 DP로 구현해보는 문제지만 의도와 다르게(?) 피보나치 수열을 굳이 구현하지 않았다. DP 연습용으로 선택한 문제인데 몇번 작성해보니 규칙성이 보여서 규칙성을 바로 때려넣어서 쉽게 해결해 버렸다.

다른 DP 문제 풀때나 이렇게 쉽게 아이디어가 떠올랐으면 좋겠는데 가장 기초 문제만 쉽게 떠오르니 아직 연습을 더 많이 해봐야겠다.