2133 타일 채우기

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

 

풀이

https://yabmoons.tistory.com/536

[ 백준 2133 ] 타일 채우기 (C++)

https://kosaf04pyh.tistory.com/236

[알고리즘 문제] 백준2133 - 타일 채우기

 

처음에 이해가 잘 되지 않았는데 간단하다.

dp[n]을 채우는 방법은 3가지가 있다.

1. dp[n-2]와 dp[2]

2. dp[n-j]와 특별한 모양 ( j={4,6,8,10...} )

3. 3*n을 채우는 특별한 모양

 

일단 특별한 모양은 매번 두 개씩 존재한다. 그림을 그려보면 쉽게 알 수 있다.

2를 해야 하는 이유는 dp[n-2]*dp[2]와 dp[2]*dp[n-2]는 겹치는 부분이 있기 때문이다.

그러므로 겹치지 않기 위해선 특별한 모양을 사용해야 한다. 

 

3*6 크기의 타일을 예로 들어보자.

dp[4]

dp[2]

dp[2]

3*4 특별한 모양

3*6 특별한 모양

 

이 세 가지만 존재하므로 dp[4]*dp[2] + dp[2]*2 + 2 = 41이다.

막상 정리해보니 어려운 문제가 아니었다.

1번 패턴과 겹치지 않게 하기 위해 2번 패턴에서 특별한 모양을 사용한 부분에서 이해가 잘 되지 않았던 것 같다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
ll dp[33];

int main(){
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n;
	dp[1]=0; dp[2]=3;
	for(int i=4; i<=n; i+=2){
		//dp[n] = dp[n-2]*dp[2] + dp[n-4]*2 + dp[n-6]*2 ... +2;
		dp[i]=dp[i-2]*dp[2];
		for(int j=4; i-j>=0; j+=2) dp[i]+=2*dp[i-j]; //특별한 모양과 3*(i-j)타일을 채우는 조합
		dp[i]+=2; //새롭게 만들어지는 조합 2개
	}
	cout<<dp[n];
    return 0;
}