문제
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 문제의 유형으로 볼 수 있다.