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

프로그래머스

[문제 설명]

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

n	result
4	11

입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

 

 

 

 

 

 

 

 

 

 

 

---

[문제 풀이]

백준에서 풀었던 2 x n 타일링 문제와 비슷한 문제다.

다른 점은 채울수있는 타일의 높이가 3이다.

높이가 3일때는 가로가 짝수개 일때만 타일을 꽉 채울수가있다.

왜냐하면 홀수 x 홀수 = 홀수 이므로 2개짜리 타일로 채울수가 없다.

따라서 우리는 가로가 2일때부터 짝수개일 경우만 고려하면 된다.

 

n = 2 일때

타일을 채울 수 있는 경우의 수는 아래와 같이 3가지 이다.

n = 4 일때

타일을 채울 수 있는 경우를 생각해보면

2칸씩, 즉 n = 2일때 타일을 채우는 경우의 수를 이용하여 채울 수 있다. (2칸, 2칸)

이때의 경우의 수는 9이다. (3 x 3)

하지만, 조심해야 할 점은 n = 4일때 4칸 모두를 사용하여 채울 수 있는 경우가 있다.

예제의 마지막 부분을 보면 아래와 같은 경우가 존재한다.

위 경우까지 고려하게 된다면 9 + 2 = 11개가 된다.

 

n = 6 일때까지만 생각해보도록 하자.

n이 6이라면 채울수 있는 경우의 수는

(2,2,2), (2,4), (4,2), (6)의 경우를 생각해 볼 수 있다.

(2,2,2)의 경우는 3x3x3 = 27이다.

(2,4)일 경우와 (4,2)일 경우를 조심해야한다.

왜냐하면 (2,2,2)의 경우와 중복 될 수 있기 때문이다.

중복되지 않는 (2,4)와 (4,2)를 계산하기 위해서는

n=4일때 마지막에 구한 4칸짜리 블록을 앞 또는 뒤에 놓는 경우 * 2칸 채우는 경우를 생각하면 된다.

이 경우는 2 * 3 * 2 = 12이다.

6칸을 한번에 채우는 경우도 존재한다. 4칸을 채울때와 동일한 구조로 2개가 생긴다.

따라서 6칸을 채우는 경우는 27 + 12 + 2 = 41이 된다.

 

6까지만 구했지만, 8, 10, 12, ⋯ 그 뒤의 숫자들도 각 칸을 채우는 경우가 2가지씩 추가된다.

점화식은 dp[n] = dp[n-2] * 3 + dp[n - 4] * 2 + ⋯ dp[2] * 2 + 2 가 된다.

dp[n-2] * 3 이라는 것은 n-2개의 모든 경우의 수에 2칸을 채우는 경우의수 3을 곱하는 것이고,

그 뒤 dp[n - 4] * 2 부터 dp[2] * 2 까지는 n - 4를 채우는 모든 경우의 수에 n - 4 개짜리를 한번에 채우는 경우의수 2을 곱한 것을 2개가 될 때까지 반복하는 것이고,

마지막에 2를 더해주는것은 n개짜리를 한번에 채우는 경우의수 2개를 더한 것이다.  

주의해야 할 점은 마지막에 꼭 1,000,000,007으로 모듈러 연산을 해줘야 한다는 것이다..

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>
#include <iostream>

using namespace std;
vector<long long> dp;
int solution(int n) {
    dp = vector<long long>(5001,0);
    dp[2] = 3;
    for(int i = 4; i <= n; i+=2)
    {
        dp[i] = dp[i-2] * 3;
        for(int j = i-4; j >= 2; j -= 2)
        {
            dp[i] += dp[j] * 2;
        }
        dp[i] += 2;
        dp[i] %= 1000000007;
    }
    return dp[n];
}