프로그래머스 - 3 x n 타일링 (C++)

Pixabay로부터 입수된 👀 Mabel Amber, who will one day님의 이미지 입니다.

 

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

프로그래머스

 이번 문제는 숫자 n이 주어졌을 때, 3 x n 크기의 직사각형에 가로 길이가 2, 세로 길이가 1인 타일을 채워넣는 방법의 수는 몇 가지인지 구하는 문제이다. 이 문제는 전형적은 동적 계획법(Dynamic Programming) 문제이다. 얼핏 보면 굉장히 쉬워보이는 문제이다. 

1. 가로 길이가 2일 때 가능한 것들

2. 가로 길이기 n일 때의 가능성 중 하나

3. 가로 길이가 4일 때의 예외들

 

왜냐햐면 위의 사진처럼 가로 길이가 2일 때 가능한 타일은 3가지 뿐이기에, 가로 길이가 n일 때는 가로 길이가 n-2일 때의 개수에 가로 길이가 2일 때의 개수 3개를 곱한 것이라고만 생각할 수 있기 때문이다. 하지만 예제의 이미지와 같은 예외도 있었기 때문에 이것을 어떻게 처리해야 하나 정말 고민이었다. 하지만, 얍문님의 문제 풀이 글을 정독하니 저 예외들을 처리할 방법을 알게 되었다.

 

4. 위의 예외들

 위의 사진과 같은 경우는 4번 사진과 같이 가로 길이가 4 이상일 때부터, 짝수일 때 생긴다. 그리고 이러한 경우들은 3번 사진과 같이 (위아래로 뒤집은) 두 가지 경우가 있다. 즉, 가로 길이가 n일 때의 점화식을 위해 고려해야할 것은 두 가지이다. 첫 번째는 2번 사진과 같이 가로 길이가 n-2인 경우와 가로 길이가 2인 경우의 조합이다. 그리고 두 번째는 4번 사진과 같은 구성들이 포함된 경우이다. 첫 번째 경우의 식은 dp[n - 2] * dp[n]으로 나타낼 수 있다. 그리고 두 번째 경우는, 4번 사진의 경우들이 2번 사진의 오른쪽 부분(가로 길이가 2인 부분)이라 생각한다면, dp[n] * 2 + dp[n - 2] * 2 + ... + dp[n - 4] * 2로 나타낼 수 있다. 따라서, 가로 길이가 n일 때의 점화식은 dp[n] = (dp[n - 2] * dp[2]) + (dp[n - 4] * 2) + (dp[n - 2] * 2) + ... + (dp[0] * 2)로 나타낼 수 있다.

 

#include <string>
#include <vector>

using namespace std;

#define MAX 5001
#define MOD 1000000007

long long dp[MAX];

long long Check(int n)
{
    if (dp[n] >= 0)
        return dp[n];

    dp[n] = Check(n - 2) * dp[2];
    dp[n] %= MOD;

    for (int x = 4; x <= n; x += 2)
    {
        dp[n] += (Check(n - x) * 2);
        dp[n] %= MOD;
    }
    
    return dp[n];
}

int solution(int n)
{
    for (int x = 0; x < MAX; ++x)
        dp[x] = -1;

    if (n % 2 == 1)
        return 0;

    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    dp[4] = 11;

    long long answer = Check(n);

    return answer;
}

---

참고한 사이트: https://yabmoons.tistory.com/536