[백준] 11726 2 x n 타일링

문제링크] https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

문제요약

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다.

풀이

다이나믹 프로그래밍 알고리즘 문제를 풀기 위해서는 점화식을 구하는 것이 가장 중요하다.

(가로가 n일 때 타일을 채우는 경우의 수) = 
 (가로가 n-1 일 때 타일을 채우는 경우의 수) X (1만큼 가로가 증가했을 때 타일을 채우는 경우의 수)
+ (가로가 n-2 일 때 타일을 채우는 경우의 수) X (2만큼 가로가 증가했을 때 타일을 채우는 경우의 수)

 이 문제의 경우 아래 그림에서 보이듯이 가로가 1만큼 증가했을 때, 한 가지. 가로가 2만큼 증가했을 때도 마찬가지로 한 가지이다. 

D[n]을 가로가 n일 때 타일링할 수 있는 경우의 수라고 했을 때

D[n] = D[n-2] +D[n-1]

이라는 점화식을 세울 수 있다. 이 점화식은 피보나치 수열과 같다.

 

코드는 c/c++ 로 작성하였습니다.

#include <stdio.h>
 
int arr[1001];
 
int dp(int x) {
    if (x == 1) return 1;
    if (x == 2) return 2;
    if(arr[x]!=0) return arr[x];
    return (arr[x] = dp(x - 2) + dp(x - 1))%10007;
     
}
int main() {
 
    int num;
    scanf("%d", &amp;num);
    printf("%d", dp(num));
 
    return 0;
}

 

다이나믹 프로그래밍을 위해서 전에 계산된 값을 배열에 저장하는 과정이 필요하다.

 	if(arr[x]!=0) return arr[x];
    return (arr[x] = dp(x - 2) + dp(x - 1))%10007;

 

arr를 전역변수로 선언하였기 때문에 모든 배열의 원소는 0으로 초기화되어 있다. 만약 이미 계산한 값이라면 arr의 원소의 값이 0이 아니기 때문에 arr의 원소를 반환하면 된다. 처음 계산하는 것이라면 점화식을 통해 값을 구한다음에 해당 인덱스에 값을 저장하면 된다. 

 

---

다이나믹 프로그래밍에서 가장 중요한 것은 "앞에서 계산한 값을 재사용" 한다는 것이다.