문제
첫번째 제출(메모리 초과)
import sys
input = sys.stdin.readline
n=int(input())
arr=[0,1,2]#n: 0 1 2
for i in range(3,n+1):
arr.append(arr[i-1]+arr[i-2])
print(arr[n]%15746)메모리 초과라는 결과가 나왔다.
https://www.acmicpc.net/board/view/72658 해당 링크의 답변을 참고하여 수정하였다.
파이썬의 정수형이 고정 메모리가 아니라는 것을 알게 되었다.
최종 제출
import sys
input = sys.stdin.readline
n=int(input())
arr=[0,1,2]#n: 0 1 2
for i in range(3,n+1):
arr.append((arr[i-1]+arr[i-2])%15746)
print(arr[n])접근 방법
- 2xn 타일링 문제와 유사하게 피보나치 수열로 풀 수 있는 문제이다.
- 배열의 인덱스 0은 사용하지 않으므로(n의 범위가 자연수) 헷갈리지 않도록 arr[1] 부터 값을 지정해준다.
f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8로f(n)=f(n-1)+f(n-2)라는 식이 성립함을 알 수 있다. 따라서 해당 값을 계산 후 15746로 나눈 값을 배열에 추가해주면 된다.
n의 개수는 무한하므로 반복문은 n+1까지 반복하도록 한다.
