백준 1720번 : 타일 코드

  흔히 보던 타일 문제여서 쉬운 이겠거니 하고 덤볐다가 의외로 어려워서 쩔쩔맸던 문제... dp만 주구장창 풀어도 아직도 어렵다. 이 문제는 좌우 대칭이 아닌 경우를 세는 문제로 보이지만 역설적이게도 좌우 대칭인 경우를 세야한다. 글로 써놓고 보니까 단순히 여집합의 관계니까 그 정도 발상은 쉬운 거 아니냐 싶겠지만 나도 그렇고 이 문제로 검색을 해보면 많은 사람들이 이 발상이 어려웠다고 한다. 발상의 전환을 잘 기억해두도록 하자.

---

  풀이

  dp의 정의는 이런 타일 방식의 문제에 자주 쓰던 그 방식이다.

 

dp[n] : 길이가 n인 판(2 ×n)을 주어진 타일(1×2, 2×1, 2×2)로 채울 수 있는 경우의 수

 

  dp는 대칭을 고려하지 않고 일반적이게 잡는다. 

---

  dp를 구하는 방법

  이 dp를 구하는 점화식은 어렵지 않기 때문에 짧게 설명하려고 한다. 길이 n짜리 판의 마지막을 세로로 긴 1×2로 채운다면 나머지 n-1짜리 판을 채우는 방법은 dp [n-1]이다. 다른 방법으로 마지막을 가로로 긴 2×1 두 개나, 2×2 하나로 채운다면 나머지 n-2짜리 판을 채우는 방법은 dp[n-2]이다.

 

dp[n] = dp[n-1] + dp[n-2] × 2

---

  답을 구하는 방법

  뒤집었을 때 겹치지 않는 경우는 애초에 좌우 대칭인 경우이다. 이 개념이 약간 이상하게 느껴질 수도 있는데 생각해보면 맞다. 뭐라고 더 설명할 길이 없으니 이해가 잘 안 된다면 곰곰이 생각해보도록 하자.... 현재 dp에 존재하는 경우들은 두 가지로 나눌 수 있다.

1. 자체적으로 좌우 대칭인 경우
2. 자체적으로 좌우 대칭이지 않은 경우

2번의 경우 뒤집었을 때 다른 누군가와 겹치게 된다. 그 경우에는 하나로 취급한다고 했으므로 절반으로 나눠줘야 한다. 그러면 우리가 구하고자 하는 타일 코드의 개수는 다음과 같다.

 

Answer = (2번 / 2) + 1번

 

  이때 1번의 경우의 수와 2번의 경우의 수를 합친 것이 dp[n]이므로 '1번 + 2번 = dp[n]'이라는 식을 이용해 식을 변형하면 이렇게 된다.

 

Answer = (dp[n] + 1번) / 2

 

  dp는 이미 구했으므로 1번의 경우의 수만 구하면 된다.

 

  자체적으로 좌우 대칭인 경우를 구하는 방법

  n이 짝수인가 홀수인가에 따라 다르다. 먼저 홀수인 경우 좌우 대칭이기 위해서는 중간에 1×2가 반드시 들어가야 한다. 그리고 그 타일을 기준으로 왼쪽과 오른쪽이 좌우 대칭인 같은 형태의 타일이 들어가야 하므로 경우의 수는 dp[(n-1)/2]이다. 그다음으로 짝수인 경우는 완전히 절반으로 나누는 경우인 dp[n/2]와 중간에 2×1 두 개가 들어가거나 2×2 한 개가 들어가는 경우인 dp[n/2 - 1]이 있다.

 

홀수 : dp[(n-1)/2]

짝수 : dp[n/2] + dp[n/2 - 1] × 2

 

#include <iostream>

using namespace std;

int n;
int dp[32];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    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 << "\n";
    }
    else
    {
        cout << (dp[n] + dp[n/2] + dp[n/2 - 1] * 2)/2 << "\n";
    }
    
    return 0;
}