https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
이 문제를 아주 처음 본다면 약간 어려울 수도 있다. 하지만 마음을 가다듬고(?) 하나씩 케이스별로 그림을 몇 개 그려보면 패턴을 이해할 수 있게 된다. 아래의 그림을 보자.
위 그림은 n이 1~4일 때의 상황을 보여준다. n=3일 때는, n=2일 때의 모양에 긴 막대(보라색)를 붙인 2가지의 경우와 n=1일 때의 모양에 누워있는 막대 2개(파랑색)를 붙인 1가지의 경우의 합으로 구할 수 있다.
n=4일 때도 마찬가지로 n=3일 때의 모양에 긴 막대(보라색)을 붙인 3가지 경우와 n=2일 때의 모양에 누워있는 막대 2개(파랑색)을 붙인 2가지의 경우의 합으로 구한다.
n=4일 때는 3가지 + 2가지 였는데, 여기서 3가지는 바로 n=3일 때의 답이다. 2가지도 바로 n=2일 때의 답이다.
즉 dp[n]=dp[n-1]+dp[n-2]의 점화식이 된다.
왜 -1과 -2인 경우만 합해서 답을 구할 수 있을까? 그것은 dp[i]는 i에서의 답을 갖고 있기 때문이다. 이전 다이나믹 프로그래밍 포스팅에서도 언급하였지만, 보통 각 셀의 값은 답을 갖고 있거나, 그 정점에서의 의미 있는 값을 갖고 있게 된다. 조건이 변했어도 처음부터 다시 시작하거나, 되돌아가지 않기 위함이다.
dp[i]은 2xi타일을 채울 수 있는 모든 경우를 갖고 있다. dp[i+1]을 구할 때 dp[i+1]내부를 아무리 뒤섞어도 결국 dp[i]에서 모두 짚어본 경우에 긴 막대기를 하나 추가함에 지나지 않는다는 것이다. 거기에 dp[i+1-2]=dp[i-1]의 경우에 누운 막대 2개를 붙여주기만 하면 된다.
알면 단순하고 코드도 짧지만 생각의 범위를 넓혀주는 좋은 문제라고 생각한다.
<주요 내용>
다이나믹 프로그래밍
<코드>
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] = 2
for i in range(3, sz):
dp[i] = dp[i-2]+dp[i-1]
print(dp[int(si())] % mod)
