백준2666 벽장문의 이동

작성일 | In

문제 링크

  • http://icpc.me/2666

문제 출처

  • 1997 KOI 고등부 3번

사용 알고리즘

  • DP

시간복잡도

  • $O(N^3)$

풀이

$i$번째로 사용할 벽장의 번호를 $V_i$라고 합시다.
이제 $V_i$번 벽장을 사용할 차례이고, 열려있는 벽장의 번호가 각각 $j, k$일 때 앞으로 이동해야 하는 횟수의 최솟값을 $D(i, j, k)$라고 합시다.

상태가 $O(N^3)$가지가 존재하고 각 상태마다 $O(1)$에 정답을 구할 수 있으므로 $O(N^3)$에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
int v[22];
int dp[22][22][22];

int f(int idx, int a, int b){
    int &res = dp[idx][a][b];
    if(res != -1) return res;
    if(idx > m) return res = 0;
    int t1 = f(idx+1, v[idx], b) + abs(a - v[idx]);
    int t2 = f(idx+1, a, v[idx]) + abs(b - v[idx]);
    return res = min(t1, t2);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> a >> b >> m;
    for(int i=1; i<=m; i++) cin >> v[i];
    memset(dp, -1, sizeof dp);
    cout << f(1, a, b);
}