[프로그래머스✈][연습문제] 3 x N 타일링 풀이

Park Ji Young·2021년 1월 13일

algorithm 프로그래머스

algorithms

목록 보기

14/26

문제풀러가기✈

👓 문제 요약

유명한 DP 문제 2 x N 타일링의 업그레이드 버전

이젠 세로의 길이가 2가 아니라 3이다!!

DP 공식을 잘 유도하면 쉽게 풀 수 있다!!

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

dp 공식을 유도해야하는데 순서대로 잘 그려보면 알 수 있다.
일단 n이 홀수면 타일링을 할 수 없으므로 답은 0 이다.

그려보면

n : 2 일 때 답은 3
n : 3 일 때 답은 0
n : 4 일 때 답은 11 이다.
n : 6 일 때는 답이 41 이다. (너무 많이 그려야해서 찾아봤다)
n : 8 일 때는 답이 153 이다. (너무 많이 그려야해서 찾아봤다)

n 이 4일 때를 생각해보자.

3X2 타일링 의 방법의 수 * 3X2 타일링의 방법의 수 = 9
n 이 4일 때만 만들 수 있는 방법 2를 더하면 11가지의 경우가 있다.

(ㅣ = ㅣ 이런식으로 가운데 가로 타일을 놓는 것)

n 이 6일 때를 생각해보자.

3X4 타일링의 방법의 수 * 3X2 타일링의 방법의 수 = 33

(3X4 에는 3X2와 3X2로 만들 수 있는 모든 경우의 수가 포함되어 있다.)
n 이 6일 때만 만들 수 있는 타일의 수 2
또 생각 해야할 것이 3 x 2 의 타일링의 방법의 수 * 2 와 3 X 4 만이 만들 수 있는 타일의 경우 2가지를 곱한 것을 더한다. = 6

왜냐하면 3X4 타일링의 방법의 수 * 3X2 타일링의 방법의 수를 할 때 오른쪽 4칸을 포함하는 오직 3X4만이 만들 수 있는 2가지 경우의 수는 들어가있지 않기 때문이다.

n 이 8 일 때는

위와 마찬가지로 3X6 일때 타일링의 방법의 수 * 3X2 일 때 타일링의 방법의 수 = 123
n 이 8일 때만 만들 수 있는 경우 : 2
3X2 일 때 타일링의 방법의 수 * 3X6일 때만 만들 수 있는 타일링의 수 = 6
3X4 일 때 타일링의 방법의 수 * 3X4일 때만 만들 수 있는 타일링의 수 = 22

감이 오는가?? 3XN 을 타일링 할 때는

3X(n-2) * 3X2 를 곱한 값
n 일 때만 만들 수 있는 2가지 경우
3X2 * (3X(n-2)일 때만 만들 수 있는 경우 2개)
3X4 * (3X(n-4)일 때만 만들 수 있는 경우 2개).... 앞의 수가 3X(n-2)에 해당할 때까지 해주면 된다.

다시 말하면

N-2 일때 경우의 수 * 3(3X2타일링의 방법의 수)
N일 때만 만들 수 있는 경우 2개
N-2k(k = 1,2,3....) N-2k가 N-2 가 될 때까지의 수 각각에 2를 곱한 값을 더해주면 된다.

🥽 소스코드 및 소스해석

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

#include <string>
#include <vector>

using namespace std;

//풀이
//ex n = 8
//더해야할 것
//answer(6) * answer(2)
//answer(2) * 2 (n 이 6일때만 존재하는 2개의 경우)
//answer(4) * 2 (n 이 4일때만 존재하는 2개의 경우)

//dp1의 인덱스는0 부터 시작되며 n이 2씩 증가할 때 마다의 값이 저장됨 n이 2,4,6,8 ....일 때
//dp2는 인덱스 0 부터 인덱스 n - 2 까지의 각각의 값 *2 의 합이 저장.

long long dp1[4096];
long long dp2[4096];
int solution(int n);
int main() {
    solution(16);
}
int solution(int n) {
    if (n % 2 == 1)
        return 0;
    dp1[0] = 3;
    dp1[1] = 11;
    dp2[1] = 6;
    for (int i = 2; i < n / 2; i++) {
        dp1[i] = (dp1[i - 1] * 3 + dp2[i - 1] + 2) % 1000000007;
        dp2[i] = (dp1[i - 1] * 2 + dp2[i - 1]) % 1000000007;
    }
    return dp1[n / 2 - 1];
}