[실버 3] 11726번: 2×n 타일링

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

11726번: 2×n 타일링

---

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

사고의 흐름

• 가장 기본적으로 2×1의 타일만 사용하는 형태를 생각해볼 수 있다. n의 값이 얼마이든 무조건 가능한 형태이기 때문이다.
• 이 기본 형태에 변화를 주어 다른 형태를 얻기 위해서는 최소 두 개의 서로 이웃한 2×1 타일을 1×2 타일로 교체해야 한다.
• 위 사실을 바탕으로 n이 1, 2, 3, … 일 때의 각각의 경우의 수를 따져 보면 규칙성을 찾을 수 있지 않을까?
• 규칙성을 따져 보니까, An을 2×n 크기의 직사각형을 채우는 방법의 수라 하면 An = nC0 + n-1C1 + n-2C2 + … + n/2Cn/2 (n이 짝수인 경우) 또는 (n+1)/2C(n-1)/2 (n이 홀수인 경우) 이라는 식이 도출되었다.
• 그런데 이런 풀이 방식이 과연 Algorithm Test의 취지에 부합할까? 일단 이 식을 사용해서 풀어본 뒤에 다른 방법도 고민해 봐야겠다.

 

• 수학식을 사용하지 말고 DP를 사용해서 풀어보자.
• 이 문제가 왜 DP지? 이전의 답을 어떻게 재활용하는지 감이 잘 안 온다.
• DP를 사용할 수 있는 조건으로 최적 부분 구조와 중복되는 부분 문제가 있는데, 이 말은 DP를 사용하는 문제는 큰 문제를 작은 문제로 나눌 수 있고 동일한 작은 문제를 반복적으로 해결해야 한다는 뜻이다.
• 그 말인 즉슨 Input N이 주어졌을 때 직사각형을 채우는 방법의 수를 구하기 위해서는 Input이 N-1, N-2, N-3, … 일때의 경우를 생각해봐야 한다?
• 그렇다면 An과 A(n-1), A(n-2), … 사이의 점화식을 파악해야겠네.
• 관계가 보일 듯 하면서도 어렵다. 시간 아까우니까 그냥 다른 사람의 코드를 보고 어떻게 했는지 살펴보자.

 

• 이 문제가 피보나치 수열이었다고? 허무하다.
• 경우의 수와 관련된 점화식을 세울 때는 유효한 기준을 세워서 Case를 잘 분류하는 게 핵심이구나. 마치 고등학생 때 확률과 통계 문제를 푸는 것 같다.

내가 작성한 소스코드

from sys import stdin
from math import comb


n = int(stdin.readline().rstrip())

ans = 0
for i in range(n//2 + 1):
    ans += comb(n-i, i)
ans = ans % 10007

print(ans)

남이 작성한 소스코드

poArlim 님:
https://poalim.tistory.com/39

피드백

• 점화식을 세울 때 현재 항과 이전 항들 사이의 관계를 파악하면 DP를 사용하여 문제를 해결할 수 있다.
• 점화식을 세울 때는 유효한 기준을 세워 Case를 잘 분류해야 한다.