2021.2.9 [백준] 피보나치 함수

다이나믹 프로그래밍

 

 

Q

 

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

A

 

다이나믹 프로그래밍을 이용할 경우, 규칙을 찾는 것이 중요하다.

밑에 메모리 초과한 코드를 보면, 그냥 DP 테이블 초기화한 다음 거기에 다 저장하려 했어서 메모리 초과가 일어났다.

그리고 중요한 점은 N은 40보다 작은 자연수 또는 0 이라는 점이다. DP 테이블을 n + 1 의 크기로 만드는 것이 아니라 41의 크기로 만들어야 하며, 점화식을 위한 반복문 또한 마찬가지이다.

0과 1의 갯수가 각각 피보나치 수열을 따르고 있으므로 DP 테이블을 두개 만들어서 문제를 해결했다.

 

코드

n = int(input()) #테스트 케이스 갯수 입력
array = list(int(input()) for _ in range(n)) #테스트 케이스 입력, 이때 각 숫자는 40을 넘지 않는다.

x = [0] * 41 #DP 테이블 초기화, 크기 주의!!
x[0] = 1
x[1] = 0

y = [0] * 41 #DP 테이블 초기화, 크기 주의!!
y[0] = 0
y[1] = 1

for i in range(2, 41): #여기서도 반복문 범위 설정 주의!!
    x[i] = x[i-1] + x[i-2]
    y[i] = y[i-1] + y[i-2]

for k in array:
    print(x[k], y[k])

 

 

오답 코드 - 메모리 초과

n = int(input())
array = list(int(input()) for _ in range(n))

d = ['0'] * 41
d[0] = '0'
d[1] = '1'

for i in range(2, n + 1):
    d[i] = d[i - 1] + d[i - 2]

for i in range(n):
    print(d[array[i]].count('0'), d[array[i]].count('1'))