[BOJ]2666 : 벽장문의 이동(c++)

[문제] : https://www.acmicpc.net/problem/2666

[풀이]

사용할 문의 인덱스를 나타내는 값(idx)과 문을 열 방향을 나타내는 값(flag)을 받는 함수를 세웠다. 현재 사용할 문이 같더라도 열려있는 문에 따라 결과값이 달라지기 때문에 cache에 사용할 문을 나타내는 값 뿐만 아니라 현재 열려있는 문을 나타내는 값 또한 메모되게 했다.
해당 인덱스에 문이 열여있는지를 체크하는 opened 배열과 현재 열려 있는 문의 인덱스를 저장하고 있는 openidx 배열을 미리 만들어 둔 다음, 문이 이미 열려있다면 상태를 그대로 두고 idx+1을 전달, 만약 열려 있는 문 2개 모두가 사용할 문보다 왼쪽에 있거나 오른쪽에 있다면 문을 왼쪽 또는 오른쪽으로 밖에 열지 못하므로(한방향으로밖에 열지못함) 그 방향으로 열고 opened와 openidx 에 상태를 바꾼다음 idx + 1을 전달한다. 그게 아니라면 문을 오른쪽으로 여는 경우와 왼쪽으로 여는 경우중 작은 쪽이 리턴되도록 한다. (나는 flag변수를 만들어 문을 열 방향을 정하였다.) 함수값이 리턴되어 ret값을 얻은 후에는 다시 opened 와 openidx 값을 원래대로 바꿔놓아야 한다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int cache[21][21][21][2];
int openidx[2];
vector<int> opened;
vector<int> Arr;

int DP(int idx, int flag)
{
    if (idx >= N) return 0;

    int& ret = cache[idx][openidx[0]][openidx[1]][flag];
    if (ret != -1)
    {
        return ret;
    }

    if (opened[Arr[idx]] == 1) {
        ret = min(DP(idx + 1, 0), DP(idx + 1, 1));
    }
    else if (openidx[0] < Arr[idx] && openidx[1] < Arr[idx])
    {
        if (flag == 1) return 2e9;
        int curop = openidx[1];
        openidx[1] = Arr[idx];
        opened[curop] = 0;
        opened[Arr[idx]] = 1;
        ret = (Arr[idx] - curop) + min(DP(idx + 1, 0), DP(idx + 1, 1));
        opened[Arr[idx]] = 0;
        opened[curop] = 1;
        openidx[1] = curop;
    }
    else if (openidx[0] > Arr[idx] && openidx[1] > Arr[idx])
    {
        if (flag == 0) return 2e9;
        int curop = openidx[0];
        openidx[0] = Arr[idx];
        opened[curop] = 0;
        opened[Arr[idx]] = 1;
        ret = (curop - Arr[idx]) + min(DP(idx + 1, 0), DP(idx + 1, 1));
        opened[Arr[idx]] = 0;
        opened[curop] = 1;
        openidx[0] = curop;
    }
    else
    {
        if (flag == 0)
        {
            int curop = openidx[0];
            opened[openidx[0]] = 0;
            opened[Arr[idx]] = 1;
            openidx[0] = Arr[idx];
            ret = (Arr[idx] - curop) + min(DP(idx + 1, 0), DP(idx + 1, 1));
            openidx[0] = curop;
            opened[Arr[idx]] = 0;
            opened[curop] = 1;
        }
        else
        {
            int curop = openidx[1];
            opened[openidx[1]] = 0;
            opened[Arr[idx]] = 1;
            openidx[1] = Arr[idx];
            ret = (curop - Arr[idx]) + min(DP(idx + 1, 0), DP(idx + 1, 1));
            openidx[1] = curop;
            opened[Arr[idx]] = 0;
            opened[curop] = 1;
        }
    }

    return ret;
}

int main(void)
{
    int K;
    cin >> K;

    opened.resize(K, 0);
    int a, b;
    cin >> a >> b;
    a--;
    b--;

    openidx[0] = min(a, b);
    openidx[1] = max(a, b);

    opened[a] = 1;
    opened[b] = 1;

    cin >> N;


    memset(cache, -1, sizeof cache);
    Arr.resize(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> Arr[i];
        Arr[i]--;
    }

    cout << min(DP(0, 0), DP(0, 1)) << endl;
}

[느낀점]

처음에는 opened 와 openidx를 바꾼후 원래대로 되돌려 놓치 않아 WA를 받았다. flag는 굳이 안쓸수도 있었지만 처음 함수를 생각할때 문을 여는 방향을 정하고자 생각을 해서 그냥 끝까지 flag를 놔둔 채 함수를 세웠다.
나름 잘 풀었다고 생각했는데 다른사람의 코드를 보고나니 내 코드가 너무 더러워 보였다..

지적 환영합니다