boj1904 01타일 (실버3) - DP

백준 문제

타일은 00 과 1 두가지 종류만 있다. 입력값 n이 들어왔을 때 조합의 수를 반환하는 문제다.

예를 들면 n = 4 일 때, 경우의 수는 5가지이다. 00 00  /  0011  /  1001  /  1100  /  1111

 

 

링크

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

1904번: 01타일

 

동적계획법(DP: Dynamic Programming) 

입력크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 문제를 해결하는 방법.

 

 

내 풀이

입력크기가 작은 부분 부터 순차적으로 생각해보자면,

 

n = 1 일때, 경우의 수는 1가지 f(1) = 1

 

n = 2 일때, 경우의 수는

(1) 00으로 시작하는 경우 1가지밖에 없음

(2) 1로 시작하는 경우, 남은 자리 1자리도 무조건 1

f(2) = 2

 

n = 3 일때, 경우의 수는

(1) 00으로 시작하는 경우, 나머지 1자리는 f(1) = 1

(2) 1로 시작하는 경우, 나머지 2자리는 f(2) = 2

f(3) = f(2) + f(1) = 3

 

n = 4 일때, 경우의 수는

(1) 00으로 시작하는 경우, 나머지 2자리는 f(2) = 2

(2) 1로 시작하는 경우, 나머지 3자리는 f(3) = 3

f(4) = f(3) + f(2) = 5

 

따라서 점화식 세워보면

f(n) = f(n-1) + f(n-2) 단, n > 2

 

# boj1904 01타일 (DP)
# 실버3

import sys
n = int(sys.stdin.readline())
dp = [0]*1000001
dp[1] = 1
dp[2] = 2
if n > 2:
    for i in range(3, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
print(dp[n])

 

 

https://github.com/yj0903/python_CodingTest/blob/main/Algorithms/DP/boj1904.py

GitHub - yj0903/python_CodingTest: python_problemSolving