문제 출처

1. 문제설명

• 2x1 타일을 이용해서 3xN 타일을 채우는 방법의 수를 return하라.

• 경우의 수가 클 수 있으니, 1,000,000,007로 나눈 값을 출력하라.

• 문제 분류
  • Implementation, Dynamic Programming

2. 알고리즘 설계

• 우선 N이 홀수인 경우 절대로 채울 수 없다.
  • 2x1의 크기이기 때문에
• 그림을 그려서 규칙(?)을 찾을 수 있었다.
  • 크기가 명시되지 않은 네모 칸은 2x1 크기의 타일이다..

• N=2일 때는 3가지의 형태가 나온다.
• N=4일 때는 2x2 형태 2개를 붙인 형태와 랜덤하게 붙인 2가지 추가 형태가 구성된다.
  • 추가 형태를 위 그림에서는 물음표(?)로 표시하였다.
• N=6일 때는 4x4 형태와 2x2 형태를 붙인 경우와 2x2 형태에 추가 형태 2가지가 구성된다.
• N=8일 때에도 같은 방식으로 진행된다.
• 그림을 토대로 점화식을 세워보면
  • F[N] = F[N - 2] * F[2] + F[N - 4] * 2 + F[N - 6] * 2 + ... + F[2] * 2 + 2이 된다.

3. 전체 코드

#include <bits/stdc++.h>
#define MOD 1'000'000'007
using namespace std;


int solution(int n) {
    if(n % 2 != 0) return 0;
    
    long long DP[5001] = {0,};
    DP[0] = 1;
    DP[2] = 3;
    
    for(int i=4; i<=n; i += 2) {
        DP[i] = DP[i-2] * 3;
        for(int j = i - 4; j >= 0; j -= 2)
            DP[i] += DP[j] * 2;
        DP[i] %= MOD;
    }
    
    return DP[n];
}

4. 소감

• 백준에 비슷한 문제들이 여럿 존재한다.
• 대부분의 문제들이 점화식이 엄청 간단한 형태라서(피보나치 같은..)
• 좀 안일하게 점화식을 세우려고 했었던 거 같다.
• 실제로 그림을 그려보니 생각보다 점화식이 복잡해서 놀랐다.