동적 프로그래밍 : 01타일(백준 1904번)

▶ 문제 : https://www.acmicpc.net/problem/1904

1904번: 01타일

##### 문제 #####
# 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 
# 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.
# 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 
# 0이 쓰인 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 
# 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을 두 개 붙인 
# 한 쌍의 00 타일들만이 남게 되었다.
# 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 
# 우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 
# 단 타일들은 무한히 많은 것으로 가정하자.

##### 입력 #####
# 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

##### 출력 #####
# 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 
# 15746으로 나눈 나머지를 출력한다.

 

▶ 접근 방법

타일이 늘어나는 규칙을 발견해야 했다.
타일이 어떤 방식으로 늘어나는지 작은 수를 통해 먼저 점화식을 만들어보고,
그 점화식이 큰 수에도 유효한지 확인하는 방식으로 해결하였다.

결국 타일이 늘어나는 경우는 1 혹은 00이 추가로 붙는 상황이다.
예를 들어,
N이 2일 때, 00, 11 총 2가지,
N이 3일 때, 001, 100, 111 총 3가지
N이 4일 때, 0011, 1001, 1100, 1111, 0000 총 5가지 
N이 5일 때, 00111, 10011, 11001, 11100, 11111, 00001, 10000, 00100 총 8가지이다.

 

▶ 풀이 코드

import sys

N = int(sys.stdin.readline().rstrip())

# 타일 정보를 담을 리스트를 만든다.
tile_memo = [0 for i in range(1000001)]

# 타일이 1개일 때, 2개일 때를 먼저 초기화 해주고
# 그 이상의 경우 발견한 점화식을 이용하여 값을 도출할 수 있도록 하였다.
def count_tile(N) :
    tile_memo[1] = 1
    tile_memo[2] = 2

    if N <= 2 :
        return tile_memo[N]

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

    return tile_memo[N]

print(count_tile(N))

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)