BAEKJOON #1904) 01타일 | DP(다이나믹 프로그래밍) | Python

백준 #9461 파도반 수열 (파이썬)

1904번: 01타일

 

💡 해보면서 패턴 찾기

붙일 수 있는 타일은 00과 1, 두 종류 밖에 없다.

따라서 n이 주어지면 (n-2) 길이 타일 앞 뒤에 00을 붙이거나 (n-1) 길이 타일 앞 뒤에 1을 붙이는 방법으로 n개의 길이를 만들 수 있다.

 

n = 1일 때는 한 가지 경우 뿐이다.

n = 2일 때는 00과 11 두 가지 경우이다.

 

n = 3일 때는 n=1일 때의 방법에 00 타일을 붙이는 방법과 n=2일 때의 방법에 1 타일을 붙이는 방법이 있다. 이때, 3가지는 중복되는 경우이므로 빼고 개수를 세면 n=3일 때 만들 수 있는 2진수는 3가지이다.

 

 

n=4일 때는 n=2일 때의 방법에 00 타일을 붙이는 방법과 n=1일 때의 방법에 1 타일을 붙이는 방법이 있다. 마찬가지로 이때에도 5개의 경우가 중복된다. 따라서 n=5일 때 만들 수 있는 2진수는 5개이다.

 

💡 점화식 세우기

위에서처럼 몇 개의 경우를 살펴보면 패턴을 발견할 수 있다. n이 주어졌을 때, n-2에서의 타일들에 앞뒤로 1을 붙이고, n-1에서의 타일들에 앞뒤로 00을 붙이므로 총 경우가 $2x{f(n-1)+f(n-2)}$가 된다. 하지만 그 중에 반절이 중복된 경우이므로 중복된 경우를 뺀 최종 개수는 $f(n-1) + f(n-2)$가 된다.

따라서 점화식은 피보나치 수열의 점화식과 같은 $f(n) =  f(n - 1) + f(n - 2)$이다.

 

💡 코드

import sys
input = sys.stdin.readline

def bin_tile(n):
	dp = [0] * 1000001
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n + 1):
		dp[i] = (dp[i - 2] + dp[i - 1]) % 15746
	return dp[n]

if __name__ == '__main__':
	n = int(input())
	print(bin_tile(n))

❗️코드 작성 시, dp 리스트에 값을 저장할 때, 15746으로 나눈 나머지를 저장해주어야한다. 왜냐하면 나머지를 저장하지 않으면 메모리 초과가 나기 때문이다. 

왜 메모리 초과가 날까?

입력값으로 100과 1000을 주어보았다. 1000만 주어도 엄청나게 큰 숫자가 list에 들어가게 된다. n의 범위가 1,000,000까지인데, 나머지 연산없이 그대로 리스트에 넣으면서 연산한다면 당연히 메모리 초과가 날 수 밖에 없다.

그렇다면 나머지 연산을 해서 저장해도 왜 결과값이 같을까? $f(n) = {f(n - 2) + f(n - 1)} % 15746$의 값과 $f(n) = {f(n - 2) % 15746} + {f(n - 1) % 15746}$의 값은 동일하기 때문이다.

 

❗️처음 dp 리스트를 선언할 때, dp = [0] * (n + 1)로 선언하면 런타임 에러가 난다. 이 부분 도저히 모르겠었는데, 여기에서 이유를 찾았다. n=1일 때는 dp 초기화 과정에서 index error가 난다!

(예외 케이스 잘 생각하기,, 생각생각생각하기 머리사용하기😇)