[BAE/<JOON> 문제풀이] 1720. 타일 코드

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

1720번: 타일 코드

서론

타일 시리즈 가면 갈수록 어려워지는 것 같다. 지금 4 x n 시리즈랑 14 x 14 판때기 채우는거 2개 남았는데 왜 비트마스킹인지 아직도 모르겠다. 이것도 골드4인데 너무 안풀렸다.

풀이

수많은 삽질이 있었지만 정답 풀이만 쓰겠다. 이 풀이의 점화식이나 아이디어도 최적이 아닌 것 같긴 하다.

풀이 유도 과정은 아래와 같다. 해결했을 때 생각 과정을 그대로 순서대로 적었다.

• 단계 별 블럭은 총 3가지 종류다.
  1. 1x2 : 서 있는 1자 블럭 ( 이하 1번블럭 )
  2. 2x1x2 : 누워있는 1자블럭이 2개 있는 블럭 ( 이하 2번블럭 )
  3. 2x2 : 바보사궁 1개 블럭 ( 이하 3번 블럭 )
• 따라서 중복을 고려하지 않은 점화식은 DP[i] = DP[i - 1] * 2 + dp[i - 2] * 4 다. ( 블럭을 앞뒤로 붙일 수 있으므로 ) 
• 제거해야 하는 중복의 종류는 2가지다.
  1. 블럭 자체의 중복 ( | | | 인데 앞뒤로 |을 추가하면 | | | | 경우 수를 2번 세게 된다. )
  2. 180도 회전 시켰을 때 중복되는 회전 중복.
• 블럭을 앞뒤로 붙인 2가지 경우가 회전 중복에 걸리지 않기 위해서는 블럭이 비대칭 패턴이어야만 한다.
• 대칭 패턴의 경우에는 2곳 중 한 곳에만 새로운 블럭을 붙일 수 있다.
• 즉, 이전 단계의 대칭 패턴 개수와 비대칭 패턴을 따로 계산해야만 한다.
• 대칭 패턴은 현재 블럭 수의 홀짝여부에 따라 달라진다. 패턴이 대칭이기 위해서는 패턴을 반으로 양분했을 때 패턴 길이가 같아야 하므로 대칭 패턴의 수는 아래와 같다.
  홀수일 때 : (i - 1) / 2 개의 대칭 패턴 + (i - 1) / 2개의 비대칭패턴 * 2
  

  

  홀수 패턴 대칭 형식

  
  짝수일 때 : i / 2 개의 대칭 패턴 + i / 2개의 비대칭 패턴 * 2 + i / 2 - 1 개의 대칭 패턴 * 2 + i / 2 - 1개의 비대칭 패턴 * 4

짝수 패턴 대칭 형식 1

짝수 패턴 대칭 형식 2

짝수 패턴 대칭 형식 3

• 대칭이 아닌 패턴은 모두 비대칭이므로 비대칭 개수는 전체 패턴 경우 수 - 대칭 패턴 경우 수가 된다.
• 문제에서 원하는 답은 회전 중복을 제거해야하므로 비대칭 패턴 수는 2로 나눈다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct dk {
	int dk, in;
};
int main()
{
	int n; cin >> n; vector<dk> dp(n + 1);
	dp[1].dk = 1; dp[0].dk = 1;
	for (int i = 2; i <= n; i++) {
		dp[i].dk = dp[i / 2].dk + dp[i / 2].in * 2;
		if (i % 2 == 0) {
			dp[i].dk += dp[i / 2 - 1].dk * 2 + dp[i / 2 - 1].in * 4;
		}
		dp[i].in = dp[i - 1].dk + dp[i - 1].in * 2;
		dp[i].in += dp[i - 2].dk * 2 + dp[i - 2].in * 4;
		dp[i].in -= dp[i].dk;
		dp[i].in /= 2;
		//cout << dp[i].dk << " " << dp[i].in << "\n";
	}
	cout << dp[n].dk + dp[n].in;
	return 0;
}