백준 11726번: 2×n 타일링 (S3) - Python 풀이

문제 설명

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

풀이 과정

클래스 3 미해결 문제로 있어서 풀었는데 너무 쉬워서 머쓱했던 문제…

규칙을 찾기 위해 n = 1부터 4까지 해보다가 현재의 모양이 과거의 모양을 이룬 것에 + 알파의 모양 이라는 것을 깨달았습니다.

1) 과거의 결과를 중복해서 사용함 2) 작은 문제의 최적이 큰 문제의 최적이 됨
⇒ DP 문제

1. 테이블 구성
f(n) = 2×n 크기의 직사각형을 채우는 방법의 수

2. 점화식 찾기
일일이 구하다 보니 피보나치처럼 f(n) = f(n-1) + f(n-2) 가 점화식으로 나왔습니다.

3. 초기값 설정
f(1)의 값은 2x1 타일 1개를 쓰는 경우의 수 1이고, 저는 f(2)부터 위의 점화식을 쓰고 싶어서 f(0)도 1로 설정해 두었습니다.

정답 코드

n = int(input())

DP = [0] * (n+1)
DP[0] = 1
DP[1] = 1

if n > 1:
    for i in range(2, n+1):
        DP[i] = DP[i-1] + DP[i-2]

print(DP[n] %  10007)

이상입니다.