[파이썬] 백준 연습문제 #11653. 골드바흐의 추측 완벽해설

문제

 

 

해설

 

피보나치 수열을 구하는 문제는 재귀 함수를 사용하는 가장 기초적인 코드이며, 앞으로 백트래킹 및 DFS를 공부하는데 있어서 잘 이해하고 넘어가야만 하는 문제이다.

 

피보나치 함수는 앞의 두 함수값이 더해진 값이 다음의 값이 되는 함수이다. 따라서 f(n) = f(n-1) + f(n-2) 의 규칙을 지니는데, 그 규칙을 그대로 코드로 구현해주면 문제없이 이 문제를 풀 수가 있다.

 

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

 

즉 위처럼 f(n)을 넣게 되면 f(n-1) + f(n-2) 를 출력해주도록 코드를 짜주면 된다. 여기서 f(0)은 0이 되고, f(1)은 1이 되기 때문에 n이 0이나 1일 경우에는 바로 정해진 값을 출력해주도록 하면 끝난다.

 

 

 

코드

import sys

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

number = int(input())
print(pibonaci(number))

 

 

결과