BOJ 1804번 랩싸기

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

2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다.

랩은 어느 크기로든 늘리거나 줄일 수 있다. N <= 1000, K <= N, B <= 15000000

처음에 dp[l][r][k] : l~r 칸까지 k개의 랩으로 덮을 때 최소 덮이는 칸 수

로 생각했는데 좌표 압축을 해도 적어도 O(N^4) 는 걸릴 것같아서 접었다. 

이 문제는 dp[i][j][k] : i 열까지 j개의 랩을 사용하여 덮을 때, i열을 덮은 상태가 k 일 때 최소 덮인 칸수.

로 O(4NK) 로 풀 수가 있다. 덮은 상태가 뭐냐면 마지막에 i열을 덮을 때 4개지 경우가 나오는데 이것을

나눠준 것이다.

마지막으로 랩을 덮은 경우가 이렇게 네가지 모양이 가능하다. 물론 음식이 존재하지않는 열은 보질 않기 때문에

안덮는 경우는 없을 것이다.

이렇게 부분 문제를 정의하여 점화식을 구하면 되는데 각 열에는 3가지 상태가 있다.

음식물이 첫번째 행에만 있는경우, 두번쨰 행에만 있는경우, 둘다 있는경우.

각 상태에 따라 점화식을 다르게 세워야 한다.

새로운 랩을 사용하거나 아니면 전 열까지 덮은 랩을 길게 늘려서 현재 열에 있는 음식까지 덮개하거나

선택을 할 수가 있을 것이고 이 것을 각 행에 대하여 다르게 적용할 수도 있을 것이다. 그래서 아래와 같은 코드가 나온다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N,K,B;
map<int,int> mp;
vector<pair<int,int> > state;
int dp[1003][1003][4];
int dist(int l, int r){
    return state[r].first - state[l].first;
}
int main() {
    memset(dp,0x3c,sizeof(dp));
    cin >> N >> K >> B;
    for(int i = 0 ; i < N; i++){
        int r,c;
        cin >> r >> c;
        mp[c] = mp[c] | (1<<(r-1));
    }
    state.push_back({0,0});
    for(auto p : mp) state.push_back(p);
    N = (int)state.size()-1;
    dp[0][0][0] = 0;
    for(int i = 1 ; i <= N; i++){
        auto p = state[i];
        int o = p.second;
        for(int k = 1; k <= K; k++){
            int& cache0 = dp[i][k][0];
            int& cache1 = dp[i][k][1];
            int& cache2 = dp[i][k][2];
            int& cache3 = dp[i][k][3];
 
            for(int j = 0 ; j < 4; j++) cache0 = min(cache0, dp[i-1][k-1][j] + 2);
            cache0 = min(cache0, dp[i-1][k][0] + 2 * dist(i-1, i));
            if(o == 1) {
                for(int j = 0 ; j < 4; j++) cache1 = min(cache1, dp[i-1][k-1][j] + 1);
                cache1 = min(cache1, dp[i-1][k][1] + dist(i-1, i));
                cache1 = min(cache1, dp[i-1][k][3] + dist(i-1, i));
            }
            if(o == 2){
                for(int j = 0 ; j < 4; j++) cache2 = min(cache2, dp[i-1][k-1][j] + 1);
                cache2 = min(cache2, dp[i-1][k][2] + dist(i-1, i));
                cache2 = min(cache2, dp[i-1][k][3] + dist(i-1, i));
            }
            if(k > 1) for(int j = 0 ; j < 4; j++) cache3 = min(cache3, dp[i-1][k-2][j] + 2);
            for(int j = 1 ; j <= 3; j++) cache3 = min(cache3, dp[i-1][k-1][j] + 1 + dist(i-1, i));
            cache3 = min(cache3, dp[i-1][k][3] + 2 * dist(i-1, i));
        }
    }
    int ans = 2e9;
    for(int i = 0 ; i < 4; i++) ans = min(ans, dp[N][K][i]);
    cout << ans;
    return 0;
}