[백준] 1788번 피보나치 수의 확장 파이썬 코드

코드1

def fibo(x):
  x = abs(x)
  if x == 0: return 0
  a,b = 0, 1
  for _ in range(2, x+1):
    a,b = b, a+b
  return b
n = int(input())
res = fibo(n)

if res == 0: print(0)
elif n < 0 and abs(n)%2 ==0: print(-1)
else: print(1)

print(res%1000000000)

파이파이로 겨우 통과한 코드이다. 메모리 초과에 대한 해답을 찾기 위해 2개만 저장했는데, 훨씬 좋은 방법이 있었다. 또 이를 뒷받침하는 근거도 첨부했으니 문제 풀 때마다 기억하면서 해결해봐야겠다.

 

코드2

def fibo(x):
  x = abs(x)
  if x == 0: return 0
  table =[0,1]
  for i in range(2, x+1):
    # 위 코드에서는 테이블에서 계산을 다 한 뒤 출력할 때 나눠줬는데
    # 여기서는 테이블을 만들면서 나눠주었다.
    # 큰 숫자를 저장하지 않아도 되어서 메모리가 절약되는 것
    # 애초에 큰 수로 나눈 나머지를 출력하라고 했을 때부터 눈치를 챘어야 한 부분일지도...
    table.append((table[i-2]+table[i-1])%1000000000)
  return table[x]
n = int(input())
res = fibo(n)

if res == 0: print(0)
elif n < 0 and abs(n)%2 ==0: print(-1)
else: print(1)

print(res)

 

해당 문제 질문 게시판 중, djm03178님의 답변

 

파이썬에서 임의의 큰 정수를 전부 int로 표현할 수 있는 이유는 그 수의 크기에 따라서 동적으로 메모리 할당량을 조절하기 때문입니다. 매우 큰 수를 표현하기 위해서는 당연히 그만큼 많은 메모리가 필요하고, 이 문제에서 나머지를 취하기 이전의 답은 메모리 제한을 넘을 만큼 커질 수 있습니다.

 

https://www.acmicpc.net/board/view/93297

글 읽기 - 메모리 초과에 관해