[백준/DP] 11726번: 2*n 타일링 (실버3, python)

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

11726번: 2×n 타일링

아이디어

DP문제이다.

우선 n이 1~5일 때를 구해서 규칙을 찾았다.

n	경우의 수
1	1
2	2
3	3
4	5
5	8
. . .

n의 경우의 수는 n-1의 경우의 수 + n-2의 경우의 수 였다.

이렇게 규칙을 찾고 찾은 식을 바탕으로 코드를 작성해보았다.

 

전체 코드

import sys 
input = sys.stdin.readline

n = int(input())
if n == 1: print(1)
else:
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % 10007

    print(dp[n])