[Algorithm]Baekjoon 1720번 : 타일 코드

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
int n;
int dp[31];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    dp[0] = 1;
    dp[1] = 1;
 
    for (int i = 2; i <= 30; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2] * 2;  
    }
 
    if (n % 2 == 1) // 홀수인경우
    {
        cout << (dp[n] + dp[(n-1) / 2]) / 2;  
    }
    else // 짝수인 경우
    {
        cout << (dp[n] + dp[n / 2] + 2 * dp[(n - 2) / 2]) / 2;
    }
}
 
 

 

이 문제를 풀기위해서는 기존의 2 * n 타일링의 결과인 dp[n]이 어떤 형태를 띄고 있는지를 알아야 한다.

 

친절한 설명은

https://beginthread.tistory.com/145

[ BOJ 백준 1720번 - 타일 코드 ] 해설 및 코드

 

을 참고. 보고 오는게 좋다.

 

먼저 기존의 조건없는 2*N타일링 문제에서의 dp[n] 값이 어떤 의미를 가지고 있는지 생각해보자.

다음그림과 설명을 보면 바로 이해된다.

 

 

https://beginthread.tistory.com/145

 

회색깔은 '완벽대칭'을 이루는 경우이고, 색깔칠해진것들은 각각 두개씩 있다.

뭐라 불러야할지 애매한데, 회색을 완벽대칭이라 했으니 색깔칠해진것들은 그냥 '대칭'이라하자.

 

여기서 '완벽대칭'인것을 X라고 하고, '대칭'을 Y라고 하자.

근데 여기서 대칭인 Y값은 쌍을 이루고있는것을 알 수 있다. 

그렇기 때문에 dp[n] = X + 2Y라고 표현한 것이다.

 

드디어 다시 문제로 돌아가면, 문제에서는 기존의 평범한 dp[n]값이 아니라 대칭일경우 중복된 값을 뺀 경우의 수를 구하고 싶다고 했다.

기존의 dp[n]값은 X인것처럼 완벽대칭, 즉 자체만으로 중복되지 않는 경우의 수도 있지만 Y처럼 쌍을 이루는 놈도 있기 때문에 문제에 부합한 결과를 도출하려면 2Y가 아니라 Y만큼만 사용해야 한다.

 

즉, 이 문제에서의 정답은 X + 2Y가 아니라 X + Y가 되야 한다.

 

그러면 완벽대칭인 X도 구해야할 것 같고, 그냥 대칭인 Y도 구해야 할 것 같아서 머리가 아프다.

그러나 우리는 기존의 dp[n]값을 활용하면 된다.

미리 작성하진 않았지만, 조건없는 2*n타일링의 dp점화식은 dp[i-1] + 2 * dp[i-2] 이다.

이 부분은 알고있다는 전제하에 글을 작성한다.

 

기존의 dp[n]은 X + 2Y니까, 여기서 완벽대칭인 X값을 더해주면 2X + 2Y가 되고, 그냥 절반으로 나눠주면 문제에서 요구하는 답인 X + Y가 나온다.

 

즉, 우리는 완벽대칭 X의 경우의 개수만 구해주면 된다.

이 경우는 n값이 홀수와 짝수일 경우 서로 다르다.

 

n값이 홀수일 경우, 가운데 세로막대기(2*1) 를 하나 세워뒀다고 가정해보자. 그러면 그 막대기의 왼쪽이든 오른쪽이든, 타일링을 어떻게 배치하던간에 맞은편에서도 대칭으로 똑같이 배치하면 완전대칭이 된다.

그렇기 때문에 홀수일 경우의 완전대칭 X의 값은 X = dp[(n-1) / 2]가 된다.

 

 

n값이 짝수일 경우, 먼저 홀수인경우와 비슷한 느낌으로, 그냥 딱 중간지점에서 왼쪽에 어떻게 배치하든, 오른편에다가 대칭되게 배치하면 된다. 즉 홀수에서의 막대기가 없는버전으로 생각하면 된다.

그렇기 때문에 먼저 X += dp[n/2] 를 해준다.

 

여기서 끝나는게 아니라 가운데에 1*2 두개 쌓은거랑 2*2짜리 한개를 홀수막대기 세워놓은거 마냥 가운데에다가 배치한다.  위 그림에서 2번째 그림이랑 6번째 그림에 해당한다. 

그다음은 마찬가지로 2*2짜리형태 블록 왼쪽에 모든 배치의 경우의 수를 다 갖다 넣으면, 맞은편에서 똑같이 대칭되게 배치하면 되기 때문에 완전대칭 형태를 만들 수 있다.

그렇기 때문에 X += 2 * dp[(n-2)/2] 이 성립된다. ( 가운데에 2*2짜리 형태를 둘 수 있는 경우의 수가 2개 ( 2*2 랑 1*2 두개쌓은형태니까 2를 곱한다)

 

즉, n값이 짝수일 경우에는

answer += dp[n/2] + 2 * dp[(n-2)/2] 가 성립된다.

 

다시한번 더 정리.

 

1. n값이 홀수일 경우, 완전대칭 X의 값 

     => dp[(n-1) /2 ];

 

2. n값이 짝수일 경우, 완전대칭 X의 값

     => dp[n/2] + 2 * dp[n/2];

 

문제에서 요구하는 답 자체는 X + Y이기 때문에, X + 2Y인 dp[n]값 + 위의 X값을 더한 후, 절반으로 나눠주면 그게 답이 된다.