[백준] 1904번 : 01타일 (파이썬)

뚝딱이 공학도·2022년 4월 25일
0

문제풀이_백준

목록 보기
123/159



문제



첫번째 제출(메모리 초과)

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)=8f(n)=f(n-1)+f(n-2) 라는 식이 성립함을 알 수 있다. 따라서 해당 값을 계산 후 15746로 나눈 값을 배열에 추가해주면 된다.
    n의 개수는 무한하므로 반복문은 n+1까지 반복하도록 한다.

0개의 댓글