[알고리즘]백준 1904 : 01타일 (파이썬)

1904번: 01타일

문제

길이 2인 ‘00’타일과 길이가 1인 ‘1’ 타일을 이용해 만들 수 있는 타일의 경우의 수를 구한다.
N = 1일 때 : {1}
N = 2일 때 : {00, 11}
N = 3일 때 : {100, 111, 001}
N = 4일 때 : {0011, 0000, 1001, 1100, 1111}

위를 통해 아래와 같은 recursion relation을 구할 수 있다.

$f(n) = f(n-1) + f(n-2)$

타일의 길이가 각각 2, 1이므로 $f(n-2)$ 개의 타일에서 길이가 2인 ‘00’타일을 붙이는 경우의 수와,

$f(n-1)$개의 타일에서 길이가 1인 ‘1’ 타일을 붙이는 경우의 수의 합인 것이다.

• 큰 문제를 작은 문제들(subproblem)로 분할 가능 - overlapping subproblem
• 하위 문제의 최적의 답을 통해 상위 문제의 최적의 답을 계산할 수 있음 - optimal substructure

위 특징을 가지는 문제이므로 Dynamic Programming 방식의 접근을 취할 수 있다.

1. Top-down

n = int(input())
memo = {}

def zero_one_tile(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    if n not in memo:
	    if n >= 15746:
		    memo[n] = (zero_one_tile(n-1) + zero_one_tile(n-2)) % 15746
	    else:
            memo[n] = zero_one_tile(n-1) + zero_one_tile(n-2)
    return memo[n]

print(zero_one_tile(n))

2. Bottom-up

n = int(input())
dp_table = {1 : 1,
            2 : 2}

def zero_one_tile(n):
    
    for i in range(3, n+1):
        if i not in dp_table:
			if i >= 15746:
                dp_table[i] = (dp_table[i-1] + dp_table[i-2]) % 15746
            else:
                dp_table[i] = dp_table[i-1] + dp_table[i-2]
    return dp_table[n]

print(zero_one_tile(n))