2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
문제 설명
더보기
피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.
문제 풀이
DP(Dynamic Programming), 동적 계획법
위의 글에서 DP에 대해 다루면서 피보나치 함수를 예로 들며 풀어보았고, 이 문제는 피보나치의 가장 기본 문제이다.
➖ 런타임 에러(Runtime Error)
n = int(input())
arr = [0] * (n + 1) # 수의 시작은 0부터이다.
arr[0] = 0
arr[1] = 1
for i in range(2, n + 1):
arr[i] = arr[i - 1] + arr[i - 2]
print(arr[n])0과 1 예외 처리를 안해주었다. 머쓱
✅[ CODE ]
0과 1에 대한 예외를 추가하여 해결.
def fibo(n):
if n == 0 or n == 1:
return n
arr = [0] * (n + 1)
arr[0] = 0
arr[1] = 1
for i in range(2, n + 1):
arr[i] = arr[i - 1] + arr[i - 2]
return arr[n]
n = int(input())
print(fibo(n))✅[ CODE ]
굳이 배열을 n + 1의 공간만큼 만들어줄 필요가 없다보니 이를 조금 수정했다.
두 가지 수를 담을 수만 있으면 되니 아래와 같이 수정했다.
def fibo(n):
arr = [0, 1]
if n == 0 or n == 1:
return n
for i in range(2, n + 1):
# answer = arr[0] + arr[1]
answer = sum(arr)
arr = [arr[1], answer]
return answer
n = int(input())
print(fibo(n))✅[ CODE ]
꼭 배열로 하지 않고, 변수로만 swap 해주면서 계산해도 된다.
n = int(input())
a, b = 0, 1
for i in range(n):
a, b = b, a + b
print(a)반응형