[백준] 2133번 : 타일 채우기

문제

 

---

풀이

 

주어진 예제 입력이 하나인데다가 대충 생각해도 알 수 있는거라 좀 힘들었다.

N의 입력이 무조건 짝수인 것만 계산했지 홀수인 경우에 0을 리턴해야 한다는 생각을 못해서 틀리기도 했고...

 

dp배열엔 N/2를 저장할 것이다. 그니까 N=2면 dp[1]에 그 답이 있고, N=4면 dp[2]에 답이 있다.

 

아무튼 N=2일 때 타일을 채우는 방법은 다음과 같다.

 

N=4라면 일단 처음 3x2를 N=2일 때처럼 채우고, 그 뒤는 dp[1]을 호출하면 된다.

 

이런식으로...

그럼 여기서 3*dp[1]이 된다.

 

근데 다른 방법으로도 타일을 채울 수 있다.

이런 모양이 2종류가 있다. 그럼 2*dp[0]을 하면 되는건가??

 

여기서 N=6일때로 가면...

이런 것도 가능하고

 

이런 것도 가능하다.

 

그럼 dp[i]에 대해서 이런 튀어나오는 블럭의 경우의 수는

j=1, 2,..., i-2인 모든 j에 대해서 2*dp[j]가 된다...

여기에 j=0인 경우도 포함할 수 있는데 그러려면 dp[0]=1로 설정해줘야 한다.

나는 그렇게 하지 않아서 저 결과에 마지막으로 2를 더해줬다.

---

소스코드

 

#include <iostream>

using namespace std;

int dp[16];

int main() {
    int N;

    cin >> N;
    if (N % 2 == 1) { //홀수인 경우
        cout << 0;
        return 0;
    }
    dp[1] = 3; //초기값
    for (int i = 2; i <= (N / 2); i++) {
        dp[i] += 3 * dp[i - 1]; //튀어나오지 않는 경우
        for (int j = i - 2; j >= 1; j--) { //튀어나오는 경우
            dp[i] += 2 * dp[j];
        }
        dp[i] += 2; //끝까지 튀어나오는 경우
    }
    cout << dp[N / 2];
}