백준 11727번: 2xn 타일링 2

문제

2×n 직사각형을 1×2, 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

#include <iostream>
#include <vector>
#pragma warning(disable: 4996)

using namespace std;


int main() {
    int n;
    cin >> n;
    int dp[1000];
    dp[0] = 1;
    dp[1] = 3;
    for (int i = 2; i < n; i++) {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
    }

    cout << dp[n-1] ;
    return 0;
}

이 문제는 DP(Dynamic Program)를 이용해서 푸는 문제이다.

​

DP문제를 푸는 방법

하나의 함수로 표현이 가능한지 확인한다.

특정 데이터 내에서 최대화, 최소화를 계산할 때 사용

특정 데이터 제거시 사용

확률 문제

변수 파악

현재 변수를 이용하여 결과값을 찾고, 이를 다시 재사용한다. 따라서 변수의 개수를 파악해야한다. (영어로 state라고 한다.)

변수간 관계식 만들기

메모하기 → 변수 값에 따른 결과값을 저장한다. ( 결과값을 저장할 배열을 미리 만들어두고, 값이 나올 때마다 저장하고, 재사용한다.)

기저 파악 → 가장 작은 문제 상태를 찾는다. (즉, 식의 초기값을 찾는 것)

​

⇒ 피보나치 배열이 전형적인 DP 문제의 유형으로 볼 수 있다.

​

• 왜 동적할당으로 dp 배열을 만들면 틀리고, 미리 범위를 설정해주면 정답인지 모르겠다ㅠ