BOJ 11727 · 2×n 타일링 2

알고리즘 분류 : 다이나믹 프로그래밍  

기초적인 DP 문제이다. BOJ 11726번 '2×n 타일링'에서 살짝 변경해주면 된다.

• D[N] : 2xN 사이즈의 직사각형을 2x2, 2x1 사각형으로 채우는 방법의 수
• D[0] = D[1] = 1
• D[N-1] : 마지막 조각을 2x1 사각형으로 채운 방법의 수
• D[N-2] : 마지막 조각을 2x2 사각형 또는 2x1 사각형 2개로 채운 방법의 수

---

C++ 소스코드

#include <cstdio>

int d[1001];

int solve(int n) {
    d[0] = d[1] = 1;
    for (int i=2; i<=n; i++) {
        d[i] = d[i-1]+2*d[i-2];
        d[i] %= 10007;
    }
    return d[n];
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
    return 0;
}

---

Python 3 소스코드

def solve(n):
    d = [0]*(n+1)
    d[0] = d[1] = 1
    for i in range(2, n+1):
        d[i] = d[i-1]+2*d[i-2]
        d[i] %= 10007
    print(d[n])

solve(int(input()))

---

참고

• 백준 온라인 저지 : BOJ 11727
• 2×n 타일링