백준 2666번 벽장문의 이동

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

벽장문의 이동 문제에서는 캐쉬에 변수가 세개가 필요합니다: 순서 인덱스, 열려있는 1번 문 인덱스 , 열려있는 2번 문 인덱스

한번에 하나의 문을 이동하므로 두 가지 경우만 고려합니다.

1. 1번 문을 이동하는 경우

2. 2번 문을 이동하는 경우

이 때, 해당 순서 인덱스가 열려있는 문들의 인덱스보다 작을 수 있기 때문에 두 수의 뺄셈(이동 거리)를 절대값으로 처리해줘야합니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 20 + 1;

 

int N, doorNum;

int order[MAX];

int cache[MAX][MAX][MAX]; //벽장 순서 인덱스, (문 열린 곳 두 곳)

 

int minMove(int orderIdx, int open1, int open2)

{

        //기저 사례: 모든 순서를 도달하면

        if (orderIdx > doorNum)

                 return 0;

 

        int &result = cache[orderIdx][open1][open2];

        if (result != -1)

                 return result;

 

        //open1 이동 혹은 open2 이동

        //현재 순서에 열려있는 문이 open1과 open2보다 작을 경우도 있으므로 절대값 abs

        result = min(abs(order[orderIdx] - open1) + minMove(orderIdx + 1, order[orderIdx], open2), abs(order[orderIdx] - open2) + minMove(orderIdx + 1, open1, order[orderIdx]));

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        int open1, open2;

        cin >> open1 >> open2;

 

        cin >> doorNum;

        for (int i = 1; i <= doorNum; i++)

        {

                 int temp;

                 cin >> temp;

                 order[i] = temp;

        }

 

        memset(cache, -1, sizeof(cache));

       

        cout << minMove(1, open1, open2) << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~