lv2 / 3 x n 타일링 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

---

문제를 보고나서 맨 처음 들었던 생각은 dfs를 통해서 모든 타일을 구해볼까 했다가, 시간초과가 날 것 같았다. 괜히 " 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요." 라는 제한사항이 걸려있는게 아닐 것이기 때문이다. 그래서 완전탐색으로 알아보자는 생각은 얼마 안가 접게 되었고, 차근차근 생각해보기로 했다.

 

N = 4일때는 2칸씩 나누어서 (N = 2일때의 경우) x (N = 2일때의 경우) 로 구해질 수 있을거라 생각했다. 어짜피 N이 홀수면 어떻게 해도 채울 수 없기 때문에(채워야 하는 타일 개수 = 홀수, 내가 쓸 수 있는 타일 개수 = 짝수) N = 2의 덩어리로 나누어 구하면 되지 않을까? 라는 생각을 했다. 그리고 이를 기점으로 "아 이문제는 DP문제구나" 라는 것을 알았다. 그러고 입출력 설명을 살펴보니, N = 2만으로 조합할 수 없는 두개의 케이스가 존재했다.

타일이 중간에 끼는 케이스

이 두개의 케이스는 N = 2만으로 조합할 수 없다. 일단 이것을 염두에 두고 N = 6일때를 생각했다.

 

N = 6일때는 N = 2 세개로 조합하면 되겠지 싶다가, 위 두개의 케이스를 생각해보니, 단순히 N = 2로만 쪼개는 문제는 아니겠거니 싶었다. 그래서 N = 4와 N = 2로 조합을 시작했다. 3 * 6 타일에서 왼쪽 기준 4칸, 2칸으로 나누고, 여기서 경우의 수를 구하면 되었다 그리고 체크하지 못한 경우가 존재하나 싶었는데, 왼쪽 기준 2칸, 4칸으로 자르고 4칸에 2개의 예외 케이스를 놓아야 하는 것도 깨달았다. "N = 4와 N = 2로 조합한 결과에 2를 곱하면 되는거 아닌가?" 싶지만 결과적으로 겹치는 경우가 존재해버린다. N = 4에서 N = 2로 조합하는 케이스의 경우, 4, 2로 쪼개서 타일링할 때와, 2, 4로 쪼개서 타일리을 할 때가 같은 경우가 나오기 때문이다.

 

그리고 N = 6에서만 나오는 2개의 예외케이스. 예외케이스는 오직 두개만 존재할 수 밖에 없다. 기본적으로 중간에 껴있는 모양이 나오려면 양 옆에 타일을 세워두고, 눕힌 타일을 계속 놓아야 한다. 왜냐고? 너비로 생각해보면 편하다. 왼쪽에 타일을 세워두면 너비 1을 쓰게 된다. 만약 중간에 다시 세워진 타일이 나온다면, 그 순간 그 모양은 N에서만 만들어지는 예외가 아닌, 그 이전에 나온 예외에 N = 2 이상의 다른 패턴을 붙인 것과 다름이 없기 때문이다. 그래서 이때의 상황을 식으로 보면

 

f(6) = f(4) * f(2) + f(2) * 2 + 2 = 3f(4) + 2f(2) + 2

 

이다. 

 

N = 8을 같은 방식으로 생각해보면, 6, 2로 나눴을때 / 4, 4로 나눴을 때 오른쪽에 예외 상황이 오는 경우 / 2, 6으로 나눴을 때 6에 예외가 오는 경우 / N = 8 예외 상황 으로 구분되고, 이를 정리해보면

 

f(8) = f(6) * f(2) + f(4) * 2 + f(2) * 2 + 2

 

가 된다.

 

이를 정리해보면,

f(N) = f(N - 2)f(2) + f(N - 4) * (예외케이스) + f(N - 6) * (예외케이스) + ... + 2

= 3f(N - 2) + 2f(N - 4) + 2f(N - 6) + ... + 2

(N은 6이상의 짝수)

이라는 식이 유도된다.

 

그리고 숫자가 커질 수 있기 때문에 자료형의 유의해야한다. 1,000,000,007(10억 7)로 나눈 나머지값을 구하라고는 하지만, 값이 7억 2천만 정도만 되어도 f(N) = 3f(N - 2) 부분에서 int형 값을 넘어가버리기 때문이다. 오버플로우를 방지하기 위해 충분히 큰 자료형을 사용하자.

 

#include <bits/stdc++.h>
#define MOD (int)(1e9+7)
using namespace std;

int solution(int n) {
    if (n % 2 == 1) return 0;

     vector<long long> dp = {0, 3, 11}; // 0, 2, 4, 6
    if (n / 2 <= 2) return dp[n / 2];
    else {
        for(int i = 2; i < n / 2; i++) {
            long long temp = (3 * dp[i] + 2) % MOD;
            for (int j = i - 1; j >= 1; j--) {
                temp += (2 * dp[j]) % MOD;
                temp %= MOD;
            }
            temp %= MOD;
            dp.push_back((int)temp);
        }
    }
    return dp[n / 2];
}