• TOC {:toc}

이 글은 백준 온라인 저지의 2747번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.06

메모리 시간 코드 길이
28776 KB 76 ms 123 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 16:35:38 16:35:40
풀이 생각 16:35:44 16:36:29
코딩 16:36:33 16:39:00
디버깅 16:39:16 16:39:41 
# 재귀 호출
# 재귀로 풀면 시간초과가 나긴 한다.
def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n + 1)

fibo(int(input()))

# 동적 계획법
N = int(input())
# N + 1개의 값을 받을 리스트를 준비한다.
F = [0] * (N + 1)
# 처음 두 값을 입력한다.
F[0], F[1] = 0, 1

for i in range(2, N + 1):
    # 이전 두 값의 합을 더한 값으로 리스트를 구성한다.
    F[i] = F[i - 1] + F[i - 2]

print(F[N])

디버그

  • 피보나치는 0부터 시작하기 때문에 N + 1개의 원소를 갖도록 리스트를 초기화해야 한다.

피드백

  • 0, 1은 굳이 인덱스로 접근해서 대입하지 않아도 초기화할 때 바로 입력하면 된다.
  • 초기화 없이 append()를 사용해도 된다.

참고 답안 1

N = int(input())
F = [0, 1]

for i in range(2, N + 1):
    F.append(F[i - 1] + F[i - 2])

print(F[N])

참고 답안 2

f1, f2 = 0, 1
s = 0
for i in range(int(input())):
    s = f1 + f2
    f1 = f2
    f2 = s
print(f1)

아이디어 & 풀이

리스트를 이용하지 않고 두 개의 변수에 계속 값을 덧씌우면서 계산한다.