백준 11727 2xn 타일링 2

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

11727번: 2×n 타일링 2

이 문제는 꼭 이전 포스팅 백준 11726: 2xn 타일링을 참조 부탁드린다. 그림 설명이 있으니.

11726과 똑같은 방식으로 푸는데 n-2의 케이스를 2배해주면 된다. 왜냐면 붙여주는 블록의 모양이 2가지이기 때문이다.

 

11726문제를 완전히 이해한다면 어렵지 않게 풀 수 있는 문제이다.

 

<주요 내용>

다이나믹 프로그래밍

 

<코드>

Python

import sys
si = sys.stdin.readline

sz, mod = int(1e3)+1, int(1e4)+7
dp = [0 for _ in range(sz)]
dp[1] = 1
dp[2] = 3

for i in range(3, sz):
    dp[i] = 2*dp[i-2]+dp[i-1]
print(dp[int(si())] % mod)

위와 같이 쓸수도 있지만 아래처럼 원소를 append해주는 식으로도 가능하다.

import sys
si = sys.stdin.readline

cases = [0, 1, 3]
for i in range(3, 1000+1):cases.append((cases[i-2]*2+cases[i-1]) % 10007)
print(cases[int(si())])