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

1. 문제 풀이

 안녕하세요? 문제 유형은 동적 계획법입니다. 데이터 크기가 작아서 메모이제이션이 필요가 있나 싶지만 혹시 몰라 넣었습니다. 질문게시판을 확인해 보니 브루트포스로도 풀리는 것 같습니다. 그냥 재귀를 사용해도 되었을 것 같네요. 함수는 다음과 같이 정의했습니다. 

int a[25];
int d[25][25][25];

int solve(int cx, int cy, int idx) {
	int nx = a[idx];
}

// (cx, cy) 위치에서 a[idx]번째로 최소거리로 이동하는 방법을 구합니다.

 

nx가 cx, cy 중 값이 같은 경우, nx가 cx보다 작은 경우, nx가 cy보다 큰 경우, nx가 cx와 cy 사이에 있는 경우로 분기를 나누었습니다. 

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x3f3f3f3f;

int n, m;
int sx, sy;
int a[25];
int d[25][25][25];

int solve(int cx, int cy, int idx) {
    if(idx == m) {
        return 0;
    }

    if(d[cx][cy][idx] != -1) {
        return d[cx][cy][idx];
    }

    int nx = a[idx];
    if(cx == nx || cy == nx) {
        d[cx][cy][idx] = solve(cx, cy, idx + 1);
    }
    else if(cx < nx && nx < cy) {
        d[cx][cy][idx] = min(solve(nx, cy, idx + 1) + abs(cx - nx), solve(cx, nx, idx + 1) + abs(nx - cy));
    }
    else if(nx < cx) {
        d[cx][cy][idx] = solve(nx, cy, idx + 1) + abs(cx - nx);
    }
    else if(cx < nx) {
        d[cx][cy][idx] = solve(cx, nx, idx + 1) + abs(cy - nx);
    }

    return d[cx][cy][idx];
}

int main() {
    fastio(nullptr, false);

    cin >> n >> sx >> sy >> m;
    for(int i = 0; i < m; i++) {
        cin >> a[i];
    }

    memset(d, -1, sizeof(d));
    cout << solve(sx, sy, 0);
}

3. 제출 결과