ACMICPC - 2×n 타일링(11726)

2xn 타일링

고3때 수업시간에 봤던 문제다. 그때는 수업시간에 DP는 이해하지 못하고 넘어갔었는데.. 아마 확통 배우던 참이라 시그마와 조합을 이용해서 엄청 복잡하게 생긴 공식을 만들어서 풀었던것 같은 기억이 있다.

이 문제 말고도 오늘은 쉬운 DP문제들을 여러개 풀어봤는데 어떻게 문제를 작게 쪼개고 패턴을 찾느냐가 중요한 것 같았다.

이 문제의 경우는 어떻게 이전 결과들을 이용해서 현재 결과를 얻어낼 수 있을 지 고민해보았다.

2 x 1일 경우는 1가지. 2 x 2일 경우에는 2 x 1짜리를 가로로 2개, 세로로 2개를 놓을 수 있으므로 2가지가 있었다.

2 x 3을 계산할때는 맨 왼쪽에 2 x 1이 있을경우, 맨 오른쪽에 2 x 1이 있을경우로 나눠서 더할까 생각해보았지만 겹치는 경우가 있었고 아예 모두 가로방향으로 놓여진 경우는 세어지지 않았다.

그래서 이 점에 착안하여 맨 왼쪽에 2 x 1이 세로로 있는 경우와 맨 왼쪽에 2 x 2 사이즈로 2 x 1짜리가 가로로 2개 놓여져 있는 경우로 나눠 보았다.

실제로 그림을 그려서 확인해보니 모두 정확하게 맞아 떨어졌다.

그렇게 나온 소스는 이러했다. (진짜.. 너무 간단하다…)

N  = input()
D = [i for i in xrange(N + 1)]

for i in range(3, N + 1):
    D[i] = D[i - 1] + D[i -2]

print D[N] % 10007

D[N]에는 2 x N 의 타일이 놓여질 수 있는 모든 경우의 수가 담겨있고, 그 경우의 수는 맨 왼쪽이 2 x 1인 경우인 D[N - 1]와 맨 왼쪽에 2 x 2 사이즈로 2 x 1짜리가 가로로 2개 놓여져 있는 경우인 D[N - 2]를 합하면 구할 수 있었다.

오늘도 열심히 풀어봤으니 앞으로도 화이팅…!