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

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

2133번: 타일 채우기

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

아래 그림은 3×12 벽을 타일로 채운 예시이다.

 

이전 문제와 똑같이 생각하면된다.

1칸을 뺐을 때와 2칸을 뺐을 때를 일단 구해본다.

그럼 위와같이 n-1일 때는 0가지, n-2일 때는 3가지가 나온다.

그러면 D[2] = 3 * D[n-2] 라는 식이 나온다.

->하지만 이 식은 정답이 아니다.

 

한번 3칸이 뺐을 경우를 계산 해보자. -> 3칸일 때는 1 x 2 막대로 만들 수 있는 경우의 수가 나오지 않는다.

 

그럼 4칸을 뺐을 경우를 게산해보자 -> 4칸일 때는 4칸을 뺐을 때만 나오는 경우의 수 2가지가 나오게된다.(기존의 경우 추가)

또한 6칸을 뺐을 경우 -> 6칸을 뺐을 때만 나오는 경우의 수 2가지가 나온다.

 

D[n] = 3 * D[n-2] + ( 2 * D[n - 4] +

                                 2 * D[n- 6] +

                                        . .

                                        . .

                                  2 * D[0] ) 

이러한 식이 나오게 된다.

 

이 식을 코드로 바꿔보자.

 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N =  Number(input);
var d = Array.from({length:1001},()=>0);

function DP(x){
        // 0일 때를 하는 이유는 d[0]일 때가 아래 식에서 나올 가능성이 있으므로
    if(x == 0) return 1;
    if(x == 1) return 0;
    if(x == 2) return 3;
    if(d[x] != 0) return d[x];
    //만약 2칸만 뺐을 때는 3가지가 나오니까 처음 식인 3* DP(x-2)를 해준다.
    var result = 3 * DP(x-2); 
    for(var i = 3; i <= x; i++){
        if(i % 2 == 0){ //짝수일 때 2가지가 추가되니까 2를 곱한 값을 계속 더해준다.
            result += 2 * DP(x - i); //여기서 만약 x가 4면 4-4로 0이 나오는 구간이 있다.
        }
    }
    
    return d[x]=result;
}
console.log(DP(N));

x===0 일 때를 추가한 이유는 원래 0일 때는 이전 문제에서도 있어야했다. 

이 문제에서는 DP[0]이라는 값이 나오기때문에 추가해줘야한다. -> 급수처럼 초항이 중요할 때는 꼭 필요

쉽게말해서 DP[4]가 들어가면 3*DP(2) ->3*3*DP[0] -> 3 * 3 * 1 이 var result = 3 * DP(x-2)에서 나온다.

근데 우리는 여기서 끝내면 안된다. 4에서 6에서 ... 특별한 경우의 수가  생기므로 더해줘야한다.

아래 for문에서 3 , 4가반복된다. 3일때는 그냥넘어가고

4일 떄 result+=2*DP(4-4)가 실행된다. 즉 x==0일 때 1을 넣어야 DP[4]일때의 2가지의 경우를 더해줄 수 있다.

D[n] = 3 * D[n-2] + ( 2 * D[n - 4] +

                                 2 * D[n- 6] +

                                        . .

                                        . .

                                  2 * D[0] )  -> 이 식이 코드로 바뀐 모습이다.

 

 

 

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

14852번: 타일 채우기 3

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

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

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

 

타일의 종류가 총 3개다.

그러면 이전에 배웠던 것처럼 1칸을 뺐을 때와 2칸을 뺐을 때를 구해보자

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

하지만 위 문제처럼 또다른 방식이 나오게된다.

4칸을 뺐을 때 위와같이 분할되지않는 2가지가 나오게 된다. 

5칸을 뺐을 때도 위와같이 분활되지않는 2가지가 추가된다. 

즉 1칸씩 증가할 때마다 2가지가 추가되게 된다.

D[n] = 2 * D[n - 1] + 3 * D[n - 2] + ( 2 * D[n - 3] +

                                                         2 * D[n - 4] +

                                                                 . .

                                                                 . .

                                                           2 * D[0] )  ->  이런 식이 나오게 된다.

 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N =  Number(input);
var d = Array.from({length:1000000},()=>0)
function DP(x){
    if(x==0) return 1;
    if(x==1) return 2;
    if(x==2) return 7;
    if(d[x]!=0) return d[x];
    var result=3*DP(x-2)+2*DP(x-1); 
    for(var i=3;i<=x;i++){
        result+=(2*DP(x-i))%100000007 
    }
    return d[x]=result%100000007
}
console.log(DP(N));

하지만 이 경우에는 시간초과가 나오게 된다. ->DP의 호출이 많아짐

4칸 뼀을 때 5칸 뺐을떄...의 식 2 * DP(x - i) : 이 식의 경우 또한 이전의 경우의 수에서 2씩 경우의 수가 추가되어 2를 곱해주는 거니까 

사실 당연히 메모제이션의 개념을 사용할 수 있다. -> 시간 단축 가능

그래서 이 때 2차원 다이나믹 프로그래밍을 이용해야한다.

이 배열의 의미는 즉

D[x][0]에 있는 수는 0칸,1칸,2칸,3칸... 일 때의 경우의 수를 넣는 것이다.

근데 이 경우의 수를 넣을려면

3*DP(x-2)+2*DP(x-1);  이식을 넣어야한다. 

그래서 DP[4][0] = DP[2][0] * 3 + DP[3] * 2 이러한 식이 완성된다.

하지만 또 4칸일때 5칸일 때... 생기는 2가지의 경우의 수도 더해줘야한다.

그래서 배열 d[2][1]에 1을 넣어준다(아까 x==1 일 때 return 1 넣어준 것처럼)  거기에 2를 곱하고 결과에 더해준다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N =  Number(input);
var d =Array.from({length:1000001},()=>Array(2).fill(0));
d[0][0] = 1;
d[1][0] = 2;
d[2][0] = 7;
d[2][1] = 0;
for(var i = 3; i <= N; i++) {
    d[i][1] = ( d[i - 1][1] + d[i - 3][0]) % 1_000_000_007
    d[i][0] = ( 3 * d[i - 2][0] + 2 * d[i - 1][0] + 2 * d[i][1]) % 1_000_000_007
}
console.log(d[N][0]);

 

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

21. 다이나믹 프로그래밍 타일링 문제 풀어보기