백준 1904 파이썬(DP)

일단 이 문제는 점화식으로 표현할 수 있다면 쉽게 풀 수 있는 문제다.
$$A_n = A_{n-1} + A_{n-2}$$
처음 1,2 까지의 값만 다른 피보나치 수열이다.

 

점화식을 알았으니
반복문 또는 재귀함수를 이용해서 풇어주면 된다.
반복문을 이용해서 풀어보았다.

# 1904번 - 01타일
# 반복문을 이용해서 - 바텀업

import sys
input = sys.stdin.readline

n = int(input())
tile_list = [0]*(n+1)

tile_list[1] = 1
tile_list[2] = 2

for i in range(3,n+1):
    tile_list[i] = (tile_list[i-1] + tile_list[i-2])%15746

print(tile_list[n])

 

이때 주의해야 할 점은 tile_list에 15746을 나누어주지 않고 변수설정을 해버리면 나중에 메모리초과가 뜨게 된다.