[python] 백준 1904: 01타일

 

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

 

 

dp문제이다.

 

#백준 1904 : 01타일

import sys

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

dp = [0] * 1000001

dp[1] = 1

dp[2] = 2

for i in range(3, n+1):

dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[n])

 

 

풀이법: 다이나믹 프로그래밍

 

아이디어: 초기 타일값을 1,2로 준 다음, 3부터 n까지의 값은 dp값끼리 더하여 나눈 나머지 값들을 출력하도록 설정하였다.