백준 2133번 C++ 타일 채우기

타일 채우기

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

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

생각하는 과정

처음에는 진짜 단순하게 생각했다.

일단 N이 홀수이면 홀수x홀수=홀수이기 때문에 2x1, 1x2크기의 타일로 벽을 채우는 것은 불가능하다.

따라서 경우의 수는 0

그리고 N이 짝수이면

i)N이 2일 때

의 세 가지 경우가 있다.

ii)N이 4일 때

N이 2일 때 각각 왼쪽 오른쪽에 하나씩 붙이는 경우 3*3 + 위 이미지의 경우 상하 반전할 경우 2

이런 식으로

dp[6]=3*dp[4] + 2*dp[2]

dp[2*i]=3*dp[2*(i-1)] + 2*dp[2*(i-2)]

라고 했더니 바로

괜히 정답률 35퍼가 아니었다...

그래서 스파게티면을 삶으면서 틈틈히 그림을 그려보고 게시판을 보면서 4일 때뿐만 아니라

6, 8일 때도 N이 증가함에 따라 새로운 경우의 수가 생긴다는 것을 깨달았다.

대충 감은 왔지만 굳이 확인하고 싶어서 일일히 다 그려봤는데 이런 결과가 나왔다

바로 전항, 전전항뿐만 아니라 전전전항, 전전....전항도 2를 곱해서 더해줘야 하는 이유는

전전항과 마찬가지로 상하로 뒤집었을 때도 세야하기 때문이다

코드

#include <iostream>
using namespace std;
int main() {
    int N;
    cin>>N;
    if(N%2==1) { puts("0"); return 0; }
    int dp[16]={0,};
    dp[1]=3, dp[2]=11;
    for(int i=3; i<=N/2; i++) {
        dp[i]=3*dp[i-1]+2;//2는 위아래 뒤집힌 것
        for(int j=i-2; j>0; j--) {
            dp[i]+=2*dp[j];
        }
    }
    cout<<dp[N/2]<<endl;
    return 0;
}