[백준/Python] 01타일

https://www.acmicpc.net/problem/1904

1904번: 01타일

n = int(input())
tile = [0, 1, 2] # 만들 수 있는 2진 수열의 개수
length = len(tile)

# 크기가 n인 2진 수열의 개수
if n >= length:
	for i in range(length, n+1):
		tile.append((tile[i-1] + tile[i-2])% 15746)

print(tile[n])

이 문제는 동적계획법 문제이기 때문에 각 n의 만들 수 있는 2진 수열의 개수를 저장해놓아야 한다. 이 문제에서는 쉽게 점화식을 파악할 수 있었다. 점화식은 f(n) = f(n-1) + f(n-2) 이다

 

1. 각 n의 만들 수 있는 2진 수열의 개수를 저장할 리스트(tile)를 만든다.

2. tile에 저장해둔 n의 2진 수열의 개수가 없다면 2진 수열의 개수를 구한다.

3. 결과를 출력한다.

 

[ 주의 사항 ]

 

메모리 초과가 발생하여 살펴보니 파이썬에서 int는 값에 따라 유동적으로 크기가 변한다. 따라서 n이 커지면 저장할 값들이 커져서 메모리가 초과되는 것이었다. 따라서 메모리 초과를 해결하기 위해서는 tile에 값을 저장할 때 15746 으로 미리 나누어서 저장해야 한다.