[백준 2666번] 벽장문의 이동 (C++)

문제링크 : https://www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, a, b, L;
int arr[21];
int dp[21][21][21]; //1번문, 2번문, 현재 위치

int func(int a, int b, int index)
{
    if(index==L) return 0; //최대 횟수 도달
    if(dp[a][b][index]) return dp[a][b][index]; //중복방지
    int used_1st = abs(arr[index]-a) + func(arr[index], b, index+1); //1번문 사용
    int used_2st = abs(arr[index]-b) + func(a, arr[index], index+1); //2번문 사용
    dp[a][b][index] = min(used_1st, used_2st); //최솟값
    return dp[a][b][index];
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> a >> b >> L;

    for(int i=0; i<L; i++)
    {
       cin >> arr[i];
    }

    cout << func(a, b, 0) ;

    return 0;
}

 

각 위치에 대해서 1번문을 사용한 경우, 또는 2번문을 사용한 경우에 따라 값을 갱신해줘야한다.

먼저 1번문을 사용하는 경우는 다음과 같다.

(현재 위치 - 1번문)의 절대값을 구해 움직인 횟수(거리)를 구해준다.

이 값을 바탕으로 다시 값을 넣어 다음 값을 탐색한다.

이 경우 넣는 값은 새롭게 생긴 문의 위치인 현재 값을 넣어준다. (현재 값이 1번문으로 이동했기 때문에 막혔던 문이 열림)

그리고 2번문인 b는 사용을 안했기에 그대로, 다음 위치에 대해 탐색해야하므로 index+1을 해준다.

 

2번문을 사용하는 경우도 거의 유사하다.

(현재 위치 - 2번문)의 절대값을 구해 움직인 횟수(거리)를 구해준다.

이 값을 바탕으로 다시 값을 넣어 다음 값을 탐색한다.

2번문의 경우에는 1번문을 사용을 안했기에 그대로 다음 탐색에 사용하고 2번문의 위치가 현재 값이므로 해당값을 2번문에 넣어준다.

 

이렇게 현재 위치에 대해서 1번문을 사용한 경우의 거리와 2번문을 사용한 경우의 거리를 구하고 이중 최솟값을 선택한다.

최솟값이 선택된 위치에 대해서 이어서 재귀를 통해 탐색을 하면서 마찬가지로 위의 방법을 통해 최솟값을 선택하고, 처음 값에 더해주게 된다.

결과적으로 누적된 합이 총 이동한 최소거리가 되며 이를 출력해주면 된다.