[Programmers Level2] 3xn타일링(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가지 방법이 있다.

 

 

 

 

 

 

 

 

 

 

 

 

[문제 풀이]

 

 

맞왜틀?????????????을 시전했던 문제

난 분명 코드를 맞게 작성 했는데 에이 혹시 설마해서 최대값 5000을 넣고 돌려보니 음수가 나왔다.

문제에서 모듈러 연산이 주어졌기 때문에 주어진 자료형 범위 안에서 해결이 가능할 것이라 생각했지만 그것은 나의 경기도 오산이였다.

그래서 함수의 자료형, 변수들을 다 long long으로 변경했다 ^^

 

무튼 다이나믹 프로그래밍 문제인 3xn 타일링을 설명해보도록 하겠다.

 

1. 테이블을 정의한다.

dp[n] = 3xn인 직사각형을 2x1 또는 1x2 타일로 채우는 방법의 수

 

2. 점화식을 정의한다.

 

점화식을 정의하기 위해 규칙을 찾을 것이다.

 

n = 1 일 때

➜ 3x1 직사각형을 2x1 또는 1x2 타일로는 채울 수 없다.

 

n = 2 일 때

➜ 3x2 직사각형을 2x1 또는 1x2 타일로 채우는 방법은 3가지이다.

 

n= 3 일 때

➜ 3x3 직사각형을 2x1 또는 1x2 타일로는 채울 수 없다.

 

여기서 알 수 있는 점은 n이 홀수일 때 3xn 직사각형을 채울 수 없다는 점이다.

그래서 n이 홀수 일 때 dp[n] = 0 이다.

 

n= 4 일 때

➜ 3x4 직사각형을 2x1 또는 1x2 타일링으로 채울 수 있는 방법은 11가지이다.(입출력 예)

 

입출력 예를 보면

n - 2 일 때 올 수 있는 경우의 수는 3가지이다.

 

여기까지만 딱 봤을 때는 점화식이 dp[n] = 3 * dp[n -2] 로 확인된다.

하지만 여기서 끝난게 아니다. n이 4일때부터 모양이 다른 것들이 2개씩 추가가 된다.

 

 

n = 4일 때 2가지이다.

 

그래서 점화식이 dp[n] = 3 * dp[n - 2] + 2 * dp[n - 4]로 알 수 있었다.

여기서 dp[0] = 1 이다.

 

n = 6 일 때는
점화식이 dp[n] = 3 * dp[n - 2] + 2 * dp[n - 4] + 2 * dp[n - 6]


n = 8 일 때는
점화식이 dp[n] = 3 * dp[n - 2] + 2 * dp[n - 4] + 2 * dp[n - 6] + 2 * dp[n - 8]

 

누적이 된다.

n이 4이상일 때부터 새로운 모양이 2개씩 추가가 되기 때문에
처음 3 * dp[n - 2]는 동일하지만,
n이 4 이상 일 때부터 n의 값에 따라 2 * dp[n - 4] + 2 * dp[n -6] ....이 누적이 되는 코드를 작성하면 된다.

 

3. 초기 값을 정의한다.

이 문제는 dp[0] = 1, dp[2] = 3 2가지를 초기값으로 정해놓는다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <algorithm>
#include <iostream>
#define MODULAR 1000000007
using namespace std;

long long dp[5001];

long long tiling(int n) {
    if(n % 2 != 0) return 0;
    if(dp[n] != 0) return dp[n] % MODULAR;
    else {
        long long result = ((3  * tiling(n-2)) % MODULAR);
        for(int i = 4; i <= n; i += 2) {
            result += ((2*tiling(n - i)) % MODULAR);
        }
        dp[n] = result;
    }
    return dp[n] % MODULAR;
}

long long solution(int n) {
    int answer = 0;
    fill(dp, dp + 5001, 0);
    dp[0] = 1;
    dp[2] = 3;

    return tiling(n);
}