2133번

2133번 - 타일 채우기

D[N] = 3 x N 타일을 1 x 2 , 2 x 1 타일로 채우는 방법의 갯수

우선 이 문제의 경우 N의 최대값이 30이기 때문에 완전탐색으로도 정답이 나온다.

그래서 완전탐색으로 풀고, DP로 한번 더 풀어보았다.

그래서 N일 때 경우의 수를 따져보면

3 x 2 블럭을 만드는 경우와 

3 x 4 , 3 x 6 , 3 x 8 , ... 3 x n 의 블럭을 만드는 경우로 나뉘어 질 수 있다.

나의 실수

=> 처음에 3 x 2 와 3 x 4 로 만드는 블럭만을 생각해서 많은 케이스를 빼먹었는데 3 x 6, 3 x 8 블럭도 ...  3 x n 블럭도 모두 다 달라서 확인해야 했다.

그래서 따져보면 

3 x 2 블럭을 만드는 방법은 3가지, 3 x n (단, n은 2가 아닌 짝수) 을 만드는 방법은 2가지가 생기게 된다. (뒤집을 수 있으므로 2가지)

이런 모든 경우의 수를 합쳐주면 된다.

<정답 코드 - 완전탐색 , DP 사용하지 않음 >

#include<iostream>
 
using namespace std;
 
int ans;
int N;
void go(int n)
{
    if (n<0)
    {
        return;
    }
 
    if (n == 0)
    {
        ans += 1;
        return;
    }
 
    for (int i = 2; i <= n;)
    {
        if (i == 2)
        {
            go(n - i);
            go(n - i);
            go(n - i);
        }
        else
        {
            go(n - i);
            go(n - i);
        }
        i += 2;
    }
 
    return;
}
 
int main()
{
    
    cin >> N;
 
    go(N);
 
    cout << ans << endl;
 
    return 0;
}

 

< 정답 코드 - DP 사용 >

#include<iostream>
 
using namespace std;
 
int ans;
int N;
int D[31];
int go(int n)
{
    if (n<0)
    {
        return 0;
    }
 
    if (n == 0)
    {
        return 1;
    }
 
    if (D[n] != 0)
    {
        return D[n];
    }
 
    for (int i = 2; i <= n;)
    {
        if (i == 2)
        {
            D[n] += 3*go(n - i);
        }
        else
        {
            D[n] += 2*(go(n - i));
        }
        i += 2;
    }
 
    return D[n];
}
 
int main()
{
    
    cin >> N;
    for (int i = 0; i < 31; i++)
    {
        D[i] = 0;
    }
 
 
    cout << go(N) << endl;
 
    return 0;
}