[KOI] 백준 2666 - 벽장문의 이동

icpc.me/2666

 

문제 이해와 그 접근

어떤 벽장을 사용하려는데 열려있다면 추가 비용 없이 그대로 이용할 수 있다.

 

만약 닫혀있다면 사용을 위해 벽장문을 밀어야 하는데 초기에 열린 벽장이 두개 주어지므로 닫혀있는 벽장을 열 수 없는 경우는 없다. 증명은 생략.

 

그렇다면 벽장문을 미는 경우는 두개로 나뉘어진다. 왼쪽으로 밀던가 오른쪽으로 밀던가.

 

동적계획법을 통해 이 두가지의 경우를 적절히 탐색하여 최소 비용을 찾아내면 될 것이다.

 

구현

dp 테이블을 이차원으로 구성했다.

 

dp[i][j] := i번째 벽장을 열려고 하고 벽장이 j와 같은 상태일 때(비트마스크) 최소 비용

 

탑다운 dp를 통해 왼쪽으로 미는 비용과 오른쪽으로 미는 비용을 비교해서 최솟값을 구하면 된다.

 

각 방향마다 벽장문을 몇개 밀어야 하는지는 비트의 & 연산을 통해 파악했다.

 

어느 한쪽이 벽장문으로 꽉차서 밀 수 없는 경우도 처리해주자.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, inst, init;
 
int seq[20];
int dp[20][1 << 20];
 
int memo(int idx, int bit);
 
int main()
{
    memset(dp, -1, sizeof dp);
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n;
    init = (1 << n) - 1;
 
    int a, b;
    cin >> a >> b;
 
    init &= ~(1 << (a - 1));
    init &= ~(1 << (b - 1));
 
    cin >> inst;
 
    for (int i = 0; i < inst; ++i)
    {
        cin >> seq[i];
        --seq[i];
    }
        
    cout << memo(0, init);
}
 
int memo(int idx, int bit)
{
    if (idx >= inst)
        return 0;
    
    int &ret = dp[idx][bit];
 
    if (ret != -1)
        return ret;
    
    ret = 0;
 
    if (!(bit & (1 << seq[idx])))
        ret += memo(idx + 1, bit);
    else
    {
        int lcost = 0, rcost = 0, shft = seq[idx], lbit = bit, rbit = bit, tmp = 1e9;
        while (shft >= 0 && bit & (1 << shft))
            --shft, ++lcost;
        
        if (shft >= 0)
        {
            lbit &= ~(1 << seq[idx]);
            lbit |= (1 << shft);
 
            tmp = min(tmp, lcost + memo(idx + 1, lbit));
        }
        
        shft = seq[idx];
 
        while (shft < n && bit & (1 << shft))
            ++shft, ++rcost;
 
        if (shft < n)
        {
            rbit &= ~(1 << seq[idx]);
            rbit |= (1 << shft);
 
            tmp = min(tmp, rcost + memo(idx + 1, rbit));
        }
 
        ret += tmp;
    }
 
    return ret;
}

사실 벽장문의 상태를 비트로 표현할 것 까지는 없고 왼쪽으로 밀지 오른쪽으로 밀지 이 두가지만 고려해서 더 효율적으로 구현할 수 있는 것 같다.