[BOJ] 11726 - 2×n 타일링

[BOJ] 11726 - 2×n 타일링

문제

문제

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

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

입력

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

출력

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

예제 입력

2

예제 출력

2

문제 해결

DP 를 이용한 문제이다. 우선 점화식을 세우기 위해 규칙을 알아보자.
n이 1일때 1개이다. n이 2일때는 2개, n이 3일때는 3개, n이 4일때는 5개이다. 따라서 공식은

dp[n] = dp[n-1] + dp[n-2]

처음 풀었을 때 헷갈렸던 점

처음 문제를 접근할떄 위에 있는 식까지는 접근을 했다. n-1 의 경우에 1x2 블록 한개를 붙이는 경우, n-2의 경우에 1x2 블록 두개를 겹쳐붙이는 경우와 2x1 블록 두개를 겹쳐붙이는 경우, 그래서 처음 세웠던 공식은

dp[n] = dp[n-1] + dp[n-2] + 1(2x1의 경우, 1x2의 경우)

하지만 n-2의 1x2 블록의 경우가 전 단계와 겹친다는 점을 생각해야한다.

처음 세웠던 공식

생각하지 못했던 경우

다시 세운 공식

이제 코드로 옮겨보겠다.

python 코드

memo = [0] * 1001
memo[0] = 1
memo[1] = 1
memo[2] = 2

n = int(input())

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

print(memo[n] % 10007)

느낀점

막무가내로 바로 풀지 말고 공식을 세우고 해야겠다고 생각했다.