[백준(BOJ)] 2133번: 타일 채우기 (Dynamic Programming, C++)

📝 문제풀이 과정

---

N이 홀수인 경우

• 2 x 1, 1 x 2 타일을 채울 수 없다.
• DP[N] = 0

N이 짝수인 경우

• DP[i] = DP[n-2]*3 : DP[n-2]에서 3 x 2에 대해 3가지 경우가 존재한다.

• 4 이상의 짝수인 경우에, 위와 같은 형태가 2개씩 존재한다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    deque<int> DP(N+1, 0);
    DP[0] = 1;
    DP[2] = 3;
    if(N%2 !=0 ) DP[N] = 0; // N == 홀수

    // N == 짝수
    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;
    }
    printf("%d", DP[N]);

}

DP[0]은 2인 경우에 필요하므로 1로 초기화해준다.

 

 

👏 결과

---