백준/11727번 :: 2xn 타일링 2 (C/C++ 구현) - DP, 메모이제이션

 

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

입력

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

 

출력

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

 

예제입력1

2

예제출력1

3

 

예제입력2

8

예제출력2

171

 

예제입력3

12

예제출력3

2731

 

코드 구현

// 백준 11727번
// 2xn 타일링 2
#include <stdio.h>

int D[1001];

int dp(int n){
    if(n <= 1){
        return 1;
    }else if(n == 2){
        return 3;
    }
    if(D[n] != 0){
        // 이미 계산된 값
        return D[n];
    }else{
        return D[n] = (dp(n-1) + 2 * dp(n-2)) % 10007;
    }
}
int main(void){
    
    int n = 0;
    scanf("%d", &n);
    printf("%d", dp(n));
    
    return 0;
}
​

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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

11727번: 2×n 타일링 2

 

관련 글

2018/05/02 - [Algorithm] - 알고리즘 :: 다이나믹 프로그래밍(DP) - 피보나치(Fibonacci) C/C++ 구현, 메모이제이

알고리즘 :: 다이나믹 프로그래밍(DP) - 피보나치(Fibonacci) C/C++ 구현, 메모이제이션

2018/05/02 - [Algorithm/백준 온라인 저지] - 백준/11726번 :: 2xn 타일링 (C/C++ 구현)

백준/11726번 :: 2xn 타일링 (C/C++ 구현)