백준 2666번 : 벽장문의 이동

  처음 이 문제를 보고 단순히 가까운 것을 swap 하기만 하면 되는 줄 알고 'dp 쓸 필요도 없겠네~!'라고 좋아하면서 덤볐다가 코드를 짜면서 좀 더 생각해보니까 가까운 것만 swap하는 것이 최소가 아니라는 것을 깨닫고.... 이진트리를 이룬다는 사실을 깨닫고... ㅠㅠ 나의 멍청스러움에 슬퍼하면서 얌전히 dp를 사용했다.

---

  풀이

 

dp[index][open1][open2]

open1과 open2번째의 벽장이 열려있을 때 index 단계의 벽장을 열기 위한 최소 이동횟수

 

  'index 단계의 벽장을 연다'라는 말이 모호해서 추가설명을 하자면 문제의 예시에 3, 1, 6, 5번 벽장을 순서대로 이용하려고 한다고 되어있다. 이때 index=2라는 것은 '두번째 단계의 벽장을 이용한다', 즉 1번 벽장을 이용하려고 한다는 뜻이다. 또 index=3이라는 것은 '세 번재 단계의 벽장을 이용한다', 즉 6번 벽장을 이용하려고 한다는 뜻이다.

 

  dp의 계산

  우선 2번과 5번 벽장이 열려있는 상태에서 3번 벽장을 사용하려고 한다면 몇 번 이동해야 할까? 답은 간단하다. 닫혀있는 3번 벽장의 문을 열려있는 2번 벽장으로 이동 시키면 됨으로 1번이다. 만약 5번 벽장을 이용하려면 2번 이동시켜야하기 때문에 최소횟수가 아니다. 이를 식으로 표현하면 다음과 같다.

 

dp[index][open1][open2] = min(abs(open1 - target), abs(open2 - target))

 

  target(= order[index])은 이용하려고 하는 벽장의 번호다. 하지만 이것만 고려하면 되는 것이 아니라 그렇게 벽장을 이동시킨 후의 상황도 고려해야한다. 예를들어보자. 1번부터 9번까지의 벽장이 있고 최초에는 1번과 9번이 열려있다고 해보자. 이때 5번 벽장을 이용 후 1번 벽장을 이용하려 한다고 하자. 이 경우 최소 횟수는 9번을 닫으며 5번을 열고 이미 열려있는 1번을 이용하는 것이다. 만약 1번을 닫으며 5번을 열면 다시 1번을 열기 위해 5번을 닫아야 해서 많은 이동이 필요하다. 따라서 그 순간의 이동 횟수만 고려하면 되는 것이 아니라 그 이후의 상황도 고려해야 한다.

 

open1을 닫으며 target을 열 경우 : abs(open1 - target) + dp[index+1][target][open2]

open2를 닫으며 target을 열 경우 : abs(open2 - target) + dp[index+1][open1][target]

 

  따라서 위의 두 경우 중 min을 취하면 된다.

 

#include <iostream>
#include <stdlib.h>
#include <cstring>

using namespace std;

int n, t;
int order[21];
int dp[21][21][21];

int count(int index, int open1, int open2)
{
    if(index > t) return 0;
    int result = dp[index][open1][open2];
    if(result != -1) return result;
    
    int target = order[index];
    dp[index][open1][open2] = min(abs(open1-target) + count(index+1, target, open2), abs(open2-target) + count(index+1, open1, target));
    
    return dp[index][open1][open2];
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp, -1, sizeof(dp));
    
    cin >> n;
    
    int open1, open2;
    cin >> open1 >> open2;
    
    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        cin >> order[i];
    }
    
    cout << count(1, open1, open2);
    
    return 0;
}