[백준] [Python] 1904번_01타일_동적 프로그래밍

문제

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

1904번: 01타일

 

풀이

# 백준 1904번 문제 - 01타일
n = int(input())
d = [0]*1000001
d[1] = 1
d[2] = 2
for i in range(3, n+1):
    d[i] = (d[i-1] + d[i-2])%15746

print(d[n])

이번 문제는 동적 프로 그래밍 알고리즘을 사용하였다.

먼저

d[1] => 1 타일 => 1

d[2] => 00, 11 타일 => 2

d[3] => 100, 001, 111 => 3

d[4] => 1100, 0011, 1001, 0000, 1111 => 5

점화식을 구해보면

d[n] = d[n-1] + d[n-2] (n>=3) 이라는 결과가 도출된다. 

인덱스는 헷갈리지 않도록 1부터 시작하였다.