[백준 1720번] 타일 코드 (C++)

문제링크 : https://www.acmicpc.net/problem/1720

1720번: 타일 코드

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, dp[31];
    cin >> N;
    
    dp[0] = 1;
    dp[1] = 1;

    for(int i=2; i<=30; i++)
    { 
        dp[i] = dp[i-1] + dp[i-2] * 2;  //1*2 + 2*2 or (2*1)*2 
    }

    if(N%2)
    {
        cout << (dp[N] + dp[N/2])/2;  //기존 + 완전대칭의 경우
    }
    else
    {
        cout << (dp[N] + dp[N/2] + 2 * dp[(N-2)/2])/2;
    }
    
    return 0;
}

먼저 dp를 통해서 구한 값은 좌우 대칭을 이루는 중복 표현이 들어간 값이다. (ex : AB, BA)

따라서 중복 값을 제거해줘야만 한다.

이때 여기서 해당 dp값에 완전대칭 (ex : AAA, ABA) 값을 1개만 가지고 있는 것을 이용한다.

 

기존 dp에 중복이 2번씩 되므로 간단하게 나누기 2를 해주기에는 위에서 완전 대칭을 이루는 값이 1개만 들어가 있기에 틀린 답이 나온다.

이를 이용해 완전 대칭을 이루는 dp 값을 더해줘서 대칭으로 인한 중복값을 2개(완전대칭, 일반대칭)로 만들고, 나누기 2를 해줌으로써 중복값을 제거한다.

 

여기서 N이 짝수와 홀수일때의 경우로 나뉜다.

홀수일때는 가운데에 1x2 타일이 들어간 경우에만 좌우가 완전대칭을 이루기에 이 경우만 확인하면된다.

이때 항상 N/2를 한 값에서 타일이 배치된다. (== (N-1/2))

 

짝수일때는 2가지의 경우가 있다.

첫번째로 간단하게 절반을 기준으로 완전대칭인 경우다.

이는 간단하게 N/2임을 알 수있다.

두번째는 타일의 가운데에 정사각형의 타일이 있고, 이를 기준으로 좌우가 완전대칭인 경우다.

정사각형이 되려면 항상 N쪽의 길이가 2여야 하므로, (N-2) / 2가 된다.

이때 정사각형을 이루는 경우의 수가, 2x2와 (2x1) x2 이렇게 2가지이므로 *2를 해줘야한다.