챕터3-19. DP | 문제 풀이4 - (2) 백준 No.2133 : 타일 채우기

타일 채우기 문제

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

문제요약

3 x N의 타일을 1 x2, 2 x 1 타일로 채우는 방법의 수 구하기

해결 방법

1. D[i] 정의
D[N] = "3 x i 를 채우는 방법의 수"

 

2. 점화식 세우기
N번째에 올 수 있는 경우의 수를 모두 조사해 봐야 한다.
길이가 2인경우, 4인경우. 6인경우, ... 모두 다른 경우의 수이다.

...

...

따라서 D[i] = 3D[i-2] + 2D[i-4] + 2D[i-6] + ... (i-k >= 0 일 동안) 이다.

타일의 모양상 i가 홀수일 때는 채우지 못하므로 i는 짝수이어야 한다.

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>

using namespace std;

int d[31];

int main()
{
    int n;
    cin >> n;

    d[0] = 1;

    for (int i = 2; i <= n; i+=2){           //(i=2, j=2), (i=4, j=2,4),  (i=6, j=2,4, 6)
        for(int j = 2; i-j >= 0; j+=2){
            if(j == 2)
                d[i] = 3 * d[i-j];
            else
                d[i] += 2 * d[i-j];
        }
    }

    cout << d[n] << "\n";
}