[백준] 1904번 - 01타일 (C++/파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 1(Dynamic programming)- 01타일

-> www.acmicpc.net/problem/1904

1904번: 01타일

 

dp	가능한 숫자
dp[1]	1
dp[2]	11	00
dp[3]	111	001	100
dp[4]	1111	0011	1001	1100	0000
...
dp[n]	dp[n - 1]	...	dp[n - 2]

n을 숫자의 길이, dp[n]에 해당하는 값을 가능한 숫자의 개수라 하자.

 

'00' 타일과 '1' 타일을 붙이는데 별 다른 제약 조건이 없다. dp[n]은 dp[n - 2]에 '00' 타일을 붙여 만들 수 있고, dp[n - 1]에 '1' 타일을 붙여 만들 수 있다.

 

따라서 점화식을 다음과 같이 세울 수 있다.

dp[n] = dp[n - 1] + dp[n - 2]

 

모든 n에 대하여 점화식을 세웠으니, 초기값(dp[1], dp[2])만 설정하고 반복문을 실행하면 정답을 도출할 수 있다.

 

 

Python 소스 코드)

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

dp = [0] * 1000001 		# 1 <= n <= 1000000

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])

 

C++ 소스코드)