백준 정렬 1715번

안녕하세요. GDSC 웹 코어 멤버 송민선입니다.

먼저 문제 분석부터 진행해보겠습니다.

문제는

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

다른 문제같은 경우는 점화식을 직접 찾아야 하는 문제가 있었는데, 이건 그냥 바로 점화식을 주어지고 구현하는 문제로 비교적 쉬운 난이도였습니다.

다만 Recursion을 잘 모르고 있다면 구현하기 힘들 수 있지만, Recursion이라는 개념을 통해 금방 해결가능합니다. (저도 처음에 Recursion을 겪고 아니 저게…. 왜? 라는 멘붕을 겪었던…)

풀이방법

import sys


def solution(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return solution(num - 2) + solution(num - 1)


number = int(sys.stdin.readline())
print(solution(number))

마무리

네 쉬운 문제였고 이런문제만 코테에 나오면 좋겠네요…