[2133] 타일 채우기 - C++

2시간 정도 고민하며 여러 가지 아이디어들을 구현해 보도 결국에는 답을 보았다.

---

문제

1. N이 홀수 라면 타일을 채울 수 없다는 것을 알아냈다.

꾸역꾸역 채워 넣어도 한 칸이 남는 것을 알 수 있다.

 

2. $3\times 2$ 타일의 경우의 수

밑에 그림처럼 3가지 가능하다

N이 4일 때부터 DP를 채워 주면 될 듯싶다.

 

3. $3 \times 4$일 때

$$ 3 \times 3 = 9$$

또 특수케이스를 고려해 줘야 하는데 아래처럼 2가지가 있다

직접 그려보면 알겠지만, 각 숫자에 존재하는 특수케이스는 두 개뿐이며 

위 두 개 이외는 모두 중복이 됨을 알 수 있다

 

총 $9 + 2 = 11$가지

 

4. $3 \times 6$일 때

$$11 \times 3 = 33$$

 

여기서부터 중복이 발생하게 되는데, 어떻게 해결해야 할까?

빗금 친 부분에는 DP [2]이기 때문에 아래 3가지 경우만 올 수 있다.

$3\times2$

그 말은 즉 3가지만 제외해 준다면 우린 중복에서 벗어날 수 있게 되는 것이다!

어떻게 위의 경우들을 DP [4]에서 제외시켜야 할까?

 

바로 특수한 케이스만을 생각해 보면 된다.

특수케이스

$$DP [2] \times 2$$

$$3 \times 2 = 6$$

 

지금 까지 총 $ 33  + 6 = 39$이고

아직 $ 3 \times 6$의 특수 케이스 2개가 남았으니

총 $39 + 2 = 41$ 임을 알 수 있다.

 

5. $3 \times 8$일 때

위의 경우에 따라 중복을 제거해야 하니, 차근차근 진행해 보자

$DP [6] \times DP [2] = 41 \times 3 = 123$

 

두 번 째부터 중복이 나오기 시작하니 $DP [4]$의 특수케이스만 고려해 준다 $DP[4] \times 2$

특수케이스만 고려한다는 말이 뭔지 어려울 수 있다, 아래 그림을 보도록 하자

위와 같이 타일이 한번 채워졌다고 가정한 후에 중복이 어떻게 생기는지 아래 그림을 통해 보자

정확히 위와 똑같은 그림이 나올 수 있다,즉 중복인 것이다.

이를 해결하기 위해서 특수케이스만 고려하는 것이다, 아래 그림을 보자

이렇게 2가지가 가능한 것이다 $DP [4] \times 2 $

 

마지막 경우는 $3 \times 6$의 특수케이스 2개를 고려하면 된다 $DP [2] \times 2$

 

 $ (DP [6] \times DP [2]) + (DP[4] \times 2) +(DP[2] \times 2) $ 그리고 $3 \times 8$의 특수테이스 2까지 더해서

 

$(DP[6] \times DP[2]) + (Dp[4] \times 2 )+ (DP[2] \times 2) + 2 = 153 $

코드

//타일 채우기
#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n;
long long dp[32];

int main(){
  init();
  cin >> n;
  if(n % 2 != 0){
    cout << 0;
    return 0;
  }
  dp[2] = 3;
  for(int i = 4; i <= n; ++i){
    dp[i] = dp[2] * dp[i-2];
    for(int j = 2; j <= i-4; j+=2)
      dp[i] += dp[j] * 2;
    dp[i] += 2;
  }
  cout << dp[n];
  return 0;
}