[Algorithm]Baekjoon 2666번 :: 벽장문의 이동

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

2666번: 벽장문의 이동

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int maxNum = 0x3f3f3f3f;
int wallClosetCount = 0;
int firstOpenCloset, secondOpenCloset;
int sequenceLength = 0;
int dp[21][21][21] = { 0 };
int targets[21] = { 0 };
 
int DFS(int left, int right, int index)
{
    if (dp[left][right][index] != maxNum) return dp[left][right][index];
    if (index == sequenceLength) return 0;
 
    int target = targets[index];
    int result = 0;
 
    if (target <= left)
    {
        result = DFS(target, right, index + 1) + left - target;
    }
    else if (target >= right)
    {
        result = DFS(left, target, index + 1) + target - right;
    }
    else
    {
        result = min(DFS(target, right, index + 1) + target - left,
                     DFS(left, target, index + 1) + right - target);
    }
 
    return dp[left][right][index] = result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> wallClosetCount;
    cin >> firstOpenCloset >> secondOpenCloset;
    cin >> sequenceLength;
 
    for (int i = 0; i < sequenceLength; ++i)
    {
        cin >> targets[i];
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    cout << DFS(firstOpenCloset, secondOpenCloset, 0);
}

 

문제설명은 벽장 어쩌고저쩌고 되어있는데, 쉽게 바꾸면 처음에 두개의 포인터(왼쪽,오른쪽)가 주어지는데 주어진 타겟들을 향해 순서대로 전부 이동할 때, 최소의 이동횟수로 이동해야하는 문제이다.

 

그냥 1차원직선형태이다 보니 그냥 가장가까운 포인터가 이동하면 되지않느냐? 라고 생각할 수도 있겠지만, 예외케이스가 존재한다.

 

즉, 타겟포인터가 왼쪽과 오른쪽 사이에 있을 때이다.

타겟포인터가 왼쪽포인터이하값이라면 그냥 왼쪽포인터로 이동시키면 되고, 오른쪽포인터이상값이라면 오른쪽포인터로 이동시켜도 된다.

 

그러나 그 사이에 있다면, 반드시 두 포인터로 각각 타겟에 접근해봐야 한다.

 

dp테이블은 다음과 같다.

-> dp[왼쪽포인터][오른쪽포인터][현재 타겟인덱스]

 

ex) dp[3][5][4] == 왼쪽포인터가 3, 오른쪽포인터가 5, 현재 타겟인덱스가 4일 때, 모든 타겟들을 체크했을 때 최소값.