다이나믹 프로그래밍(Dynamic Programming) - 타일링 문제

다이나믹 프로그래밍 기법의 기본인 타일링 문제를 알아보자.

 

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

11726번: 2×n 타일링

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

 

이 문제를 푸는 방법은 먼저 n=1일 때 n=2 일 때 n=3일 때를 구하면서 규칙성을 찾아야한다.

그러면 n = k 일 때를 가정해보자.

만약에  n = k-1 인 경우에서 1칸을 앞에 뺐을 때 나올 수 있는 경우의 수는 1개다 (1X2 막대가 하나 붙을 수 있다.)

그리고  n= k-2 인 경우에서 2칸을 앞에 뺐을 때 나올 수 있는 경우의 수는 1개다 (2X1  막대가 두개 붙여서 가능하다.)

 

여기서 k-2인 경우에 1x2 막대로 두개를 세우는 경우는 왜 포함하지않는지?

-즉 k-1에서 1x2를 하나 세운 경우에 포함되기 때문입니다.

 

 

쉽게 설명

현재 n = 3일 때의 경우를 그림으로 그렸다.

이때 앞에서 한칸을 뺐을 경우를 그림으로 그린다.

 

즉 D[n] = D[n-1] +D[n-2] 라는 식이 도출된다.

 

근데 왜 3칸을 뺀 경우는 하지않는지?? -> 이또한 n-1에 포함되어있음 위에 쉽게 설명한 부분보면 이해가능

즉 D[n-1]의 계산에서  포함이된다. D[n-1] = D[n-2]+D[n-3] 이니까

 

그럼 코드로 살펴보자

이전에 배웠던 메모제이션도 포함시켜서 더욱 빠르게 계산한다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N =  Number(input);
var d = Array(1001).fill(0)
function DP(x) {
    if(x==1) return 1;
    if(x==2) return 2;
    if(d[x] !=0) return d[x]; //메모제이션
    return d[x] = (DP(x - 1) + DP(x - 2)) % 10007;
}
DP(N);
console.log(DP(N));

이렇게 된다

 

 

 

 

그러면 이제 응용이 된 문제를 풀어보자

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

 

2×n 타일링 2

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

62575

37333

29936

59.070%

문제

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

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

입력

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

출력

 

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

.

 

 

이번의 경우에는 도형을 3개를 사용가능하다.

그래서 D[n] = D[n - 1]  +  2*D[n - 2] 라는 식이 나오게 된다.

 

코드로 바꿔보면 아래와 같다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N =  Number(input);
var d = Array.from({length:10001},()=>0);
function DP(x) {
    if(x==1) return 1;
    if(x==2) return 3;// 2칸일 때 3가지의 경우의 수가 나오므로
    if(d[x] !=0) return d[x]; //메모제이션
    return d[x] = (DP(x - 1) + 2 * DP(x - 2)) % 10007; // DP(x-2) 에 2를 곱해준다.
}
DP(N);
console.log(DP(N));

x==2  즉 2칸일때 3개의 경우의 수가 나오는 것을 적어줘야한다.

 

 

 

출처

https://blog.naver.com/ndb796/221233586932