[프로그래머스][LV2][C++]3*n 타일링

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

프로그래머스

 

문제를 봤을 때 DP로 풀면 좋을 것 같다고 생각을 했다. 그러려면 일반 점화식을  도출해내야한다. 

문제를 생각해보면 짝수에서만 가능하다는 것을 알 수 있다. 그리고 일반적인 경우를 생각해보자면

 

• n=0인 경우:
  • 타일을 채울 수 없는 경우로, 한 가지 방법이 존재-> 아무것도 하지 않는 방법.
• n=2인 경우:
  • 가로로 타일 3개 배치
  • 세로로 2개를 위로 쌓아 배치
  • 세로로 2개를 아래로 쌓아 배치 
• n=4인 경우:
  • 3×2 크기의 바닥을 두 번 채우는 경우와 유사하게 생각할 수 있다.

이제 점화식을 도출해보자 

3×n 크기의 바닥을 채우는 방법을 찾기 위해 3×(n−2) 혹은 그 이하의 크기에서 타일을 어떻게 배치하는지 생각해보자

n의 경우의 수를 구하려면 일단 n-2번째와 n-4.. 0이 될때까지의 경우의 수를 모두 더 해주어야한다. 이때 n-4의 패턴부터는 좌우 대칭적으로 배치할 수 있기 때문에 곱하기2를 해준다.

코드로 구현하면 다음과 같다

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;
//dp활용 
//짝수일때만 계산가능

int solution(int n) {
   if (n % 2 != 0) return 0; // 홀수일 경우 0 반환
    
    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // base case
    dp[2] = 3; // 기본적인 2x3 타일 배치 방법의 수
    
    for (int i = 4; i <= n; i += 2) {
        dp[i] = dp[i - 2] * dp[2];
        for (int j = i - 4; j >= 0; j -= 2) {
            dp[i] += dp[j] * 2;
        }
        dp[i] %= MOD;
    }
    
    return dp[n];
}