[백준/Baekjoon] 2133 타일 채우기 C++ :: Dynamic Programming & bit field

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

---

1. Logic

비트필드를 사용하여 현재 위치에서 블럭을 놓은 후 생기는 모양에 대해서 처리해줬다.

그림으로 보면

이 모양(1 | (1<<1))인경우 에서 2x1모양의 타일을 놓을 수 있는 경우는 3번째 칸에 가로로 한개의 블럭을 놓을 수 있는 경우 밖에 없으므로 이다음 모양은 아래와 같이 된다.  3번째 칸에 블록이 있는 경우

지금 경우(1<<3)는 첫번째 두번째 칸에 블럭을 놓아야 하는데 가로로 두개를 놓는 경우와 세로로 하나를 놓는 경우가 있다.

 

이렇게 지금 있는 인덱스에서 비어있는 곳을 체크한 후 상황에 맞게 넣어주고 다음번에 나올 상황을 재귀로 넘겨주면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int dp[8][93];

int solve(int type, int idx) {
    if(idx == n) {
        if(type == 0)  return 1;
        else return 0;
    }
    
    int &ret = dp[type][idx];
    if(ret != -1) return ret;

    ret = 0;

    if(type == 0) {
        ret += solve(1 | (1 << 1) | (1 << 2), idx + 1);
        ret += solve(1, idx + 1);
        ret += solve((1 << 2), idx + 1);
    }
    else if (type == 1) {
        ret += solve(0, idx + 1);
        ret += solve(((1 << 1) | (1 << 2)), idx + 1);
    }
    else if (type == (1 << 1)) {
        ret += solve(1 | (1 << 2), idx + 1);
    }
    else if (type == (1 << 2)) {
        ret += solve(0, idx + 1);
        ret += solve((1 | (1 << 1)), idx + 1);
    }
    else if (type == (1 | (1 << 1))) {
        ret += solve(1 << 2, idx + 1);
    }
    else if (type == ((1 << 1) | (1 << 2))) {
        ret += solve(1, idx + 1);
    }
    else if (type == (1 | (1 << 2))) {
        ret += solve((1 << 1), idx + 1);
    }
    else if (type == (1 | (1 << 1) | (1 << 2))) {
        ret += solve(0, idx + 1);
    }

    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n;

    cout << solve(0, 0);
}

 

 

---

3. Feedback

난 DP를 점화식을 세워서 BottomUp으로 푸는 방법을 잘 모르겠다. 너무 직관적이지 않아서 이해가 안된다. 난 Topdown이 좋다~! 비트필드를 활용하는 방법도 좋은것 같다. 경우의 수가 적으면 비트필드로도 생각해봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90