타일링(DP)

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

프로그래머스

 

DP 문제인만큼 이전의 상황들을 사용하여 새로운 상황을 풀어나간다.

 

길이가 N인 직사각형을 채우는 방법은 다음과 같이 나눌 수 있다.

1. 길이가 N-1인 직사각형을 채우는 방법에서 가장 오른쪽에 세로 타일 1개를 추가한다.

2. 길이가 N-2인 직사각형을 채우는 방법에서 가장 오른쪽에 가로 타일 2개를 추가한다.

 

길이가 N-2인 직사각형에서 세로 타일을 2개 추가하는 경우는 이미 1번에서 모두 나오게 된다.

 

DP[N] = DP[N-1] + DP[N-2]

 

#include <string>
#include <vector>

int DP[60001] = { 0, };

int solution(int n)
{
    DP[0] = 1;
    DP[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        // 바로 전 타일에서 세로타일 하나 추가
        // 전전 타일에서 가로타일 2개를 추가
        DP[i] = (DP[i - 1] + DP[i - 2]) % 1000000007;
    }
    int answer = DP[n];
    return answer;
}

---

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

프로그래머스

 

가로의 길이가 3인 직사각형에선 고려해야할 사항이 추가로 생기게 된다.

 

1. 길이가 짝수일때만 타일을 채울 수 있다.

2. 길이가 4 이상일때 기존의 모양과 다른 형태의 타일 배열이 생기게 된다.

 

기본적인 타일의 배열은 다음 셋 중의 하나의 형태를 갖게된다.

 

그러므로 길이가 N-2인 직사각형을 채우는 경우의 수에서 3배를 곱하면 길이가 N인 직사각형을 채우는 경우의 수에 포함된다.

 

DP[N] = DP[N-2] * 3 + a

 

근데 길이가 4를 넘어가면 기존의 타일 배열로는 만들 수 없는 특이한 타일의 배열이 추가된다.

짝수 길이마다 이러한 특이한 배열은 2개씩 생겨나므로 N-4, N-6, N-8,...0까지 2배씩 곱하여 더해주어야 한다.

 

DP[N] = DP[N-2] * 3 + DP[N-4] * 2 + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2

※DP[0] = 1, DP[2] = 3

 

이러한 점화식을 사용하여 문제를 정리하여 풀면 된다.

 

DP[N] = DP[N-2] * 3 + DP[N-4] * 2 + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2

DP[N-2] = DP[N-4] * 3 + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2

 

DP[N] = DP[N-2] * 3 + DP[N-2]

+ DP[N-4] * 2 + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2

- (DP[N-4] * 3 + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2)

 

DP[N] = DP[N-2] * 4 - DP[N-4]

 

저장되는 값은 1000000007로 나눈 값임에 유의하여야 한다

 

#include <string>
#include <vector>
using namespace std;

long long DP[5001] = { 0, };

int solution(int n)
{
    if (n % 2 == 1) return 0;
    DP[0] = 1;
    DP[2] = 3;
    // DP[n] = DP[n-2] * 3 + DP[n-4] * 2 + DP[n-6] * 2 +...+ DP[0] * 2
    // DP[n-2] = DP[n-4] * 3 + DP[n-6] * 2 +...+ DP[0] * 2
    // DP[n] = DP[n-2] * 4 - DP[n-4]
    for (int i = 4; i <= n; i += 2)
    {
        if (DP[i - 2] < DP[i - 4]) DP[i-2] += 1000000007;
        DP[i] = (DP[i - 2] * 4 - DP[i - 4]) % 1000000007;
    }
    return (int)DP[n];
}