백준 1904 | 01타일 (DP-파이썬)

문제 출처 : https://www.acmicpc.net/problem/1904

문제

• 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물했다.
• 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일이다.
• 어느날 짓궃은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낮장의 타일들을 붙여서 한 쌍으로 이루어진 00타일을 만들었다.
• 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두개 붙인 한 쌍의 00타일들만 남았다.
• 그러므로 지원이는 타일로 더 이상 크기가 n인 모든 2진 수열을 만들 수 없게 되었다.
• 예를 들어 n = 1 일 때 1만 만들 수 있고, n = 2일 때는 00, 11을 만들 수 있다.
• n = 4 일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
• 우리의 목표는 n이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.
• 타일은 무한히 많은 것으로 가정하자

문제 접근 방법

• 타일의 개수가 늘어남에 따라 이전 타일의 수와의 관계를 어떻게 점화식으로 정리할 수 있을 것인가? 에 대한 고민
• $dp[n]$ 은 ($dp[n-1]$ 에 " $1$ " 타일 하나를 붙이는 경우의 수) + ($dp[n - 2]$에 " $00$ " 인 타일 묶음 하나 (붙어 있는 "$0$" 타일 2개)) 를 붙이는 경우의 수이다.
  • $dp[n] = dp[n-1] + dp[n-2]$

코드

import sys

n = int(sys.stdin.readline())

# 메모이제이션을 위한 리스트 선언
memo = [0] * 1000001

def count_tile(x):

    if x < 3:
        return x
    if memo[x]:
        return memo[x]

    memo[x] = count_tile(x - 2) + count_tile(x - 1)
    return memo[x]

print(count_tile(n))