본문 바로가기

알고리즘 관련/BOJ

BOJ)2618 경찰차

문제:icpc.me/2618


경찰차 두대가 사건을 순서대로 처리할 때 가장 적은 거리를 이동하도록 사건을 배치하는 경우와 거리를 출력하는 문제이다.


dp[x][y] = 경찰차 1이 x번째 사건을 경찰차 2가 y번째 사건을 마지막으로 처리하였을 때 이동한 거리의 합의 최솟값으로 정의한 뒤 문제를 해결해주면 된다.


점화식은 dp[x][y] = min(dp[prev][y]+ dist(prev,x) , dp[x][prev] + dist(prev,y))이다.


소스에서는 바텀업 방식으로 구현하여 테이블의 정의가 약간 바뀌었다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1987654321
using namespace std;
int dp[1001][1001], n, w, back[1001];
pair<intint> d[1001];
int getdist(pair<intint> a, pair<intint> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
int func(int x, int y) {
    if (x == w || y == w)return 0;
    int &ret = dp[x][y];
    if (ret != -1)return ret;
    int fir, sec;
    if (!x) 
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], { 1,});
    else 
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], d[x]);
    if (!y)
        sec = func(x, max(x, y) + 1+ getdist(d[max(x, y) + 1], { n,n });
    else
        sec = func(x, max(x, y) + 1+ getdist(d[max(x, y) + 1], d[y]);
    return ret = min(fir, sec);
}
void solve(int x, int y) {
    if (x == w || y == w) return;
    int fir, sec;
    if (!x)
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], { 1,});
    else
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], d[x]);
    if (!y)
        sec = func(x, max(x, y) + 1+ getdist(d[max(x, y) + 1], { n,n });
    else
        sec = func(x, max(x, y) + 1+ getdist(d[max(x, y) + 1], d[y]);
    if (fir < sec) {
        back[max(x, y) + 1= 1;
        solve(max(x, y) + 1, y);
    }
    else {
        back[max(x, y) + 1= 2;
        solve(x, max(x, y) + 1);
    }
}
int main() {
    memset(dp, -1sizeof(dp));
    scanf("%d%d"&n, &w);
    for (int i = 1; i <= w; i++)
        scanf("%d%d"&d[i].first, &d[i].second);
    printf("%d\n", func(00));
    solve(00);
    for (int i = 1; i <= w; i++)
        printf("%d\n", back[i]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)7579 앱  (0) 2017.04.05
BOJ)2157 여행  (0) 2017.04.05
BOJ)2688 줄어들지 않아  (0) 2017.04.04
BOJ)2230 수 고르기  (0) 2017.04.04
BOJ)9463 순열 그래프  (1) 2017.04.03