11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
내 사번과 똑같은 11727 번 문제를 우연히 발견해서 풀어보았다.
2xn 타일링 문제는 쉽게풀려고 한다면 엄청 쉬운 dp문제로, 점화식을 잘세우면 끝난다.
솔직히 2x3까지의 경우의수를 구하고 2x1, 2x2인 경우를 활용하여 2x3의 경우의 수를 다 시도해보면 쉽게 나올 수 있다.
dp[1] = 1
dp[2] = 3
dp[3] = 5
이므로,
dp[3] = dp[2] + dp[1] + 1
dp[3] = (dp[2] * dp[1]) + 2
dp[3] = dp[1] + dp[2] * 2
등등의 조합을 시도해보면된다.
물론 점화식이 눈에 보이는 사람은 더욱 쉬울 것이다.
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] *(1000+1)
dp[1] = 1
dp[2] = 3
dp[3] = 5
for i in range(3,1000+1):
dp[i] = dp[i-1]+dp[i-2]*2
print(dp[n]%10007)
