BOJ 2618: 경찰차

작성일

https://www.acmicpc.net/problem/2618

  • 2월동안 187문제 풀기(지난달 누적 87개) (62/187)
  • DP를 잘못 만들면 재앙이 된다는걸 보여주는 문제.
  • 어제 풀다가 멘붕왔음 -_-.. 오늘 다시 생각을 가다듬은 뒤에 성공
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
#include <bits/stdc++.h>
using namespace std;

const int SZ = 1001;
int N, W;
int dp[SZ+1][SZ+1];
struct Coord {int x,y;};
vector<Coord> arr;

struct Pos {int p1,p2,v;};
Pos track[SZ+1][SZ+1];

void fillInput() {
  cin >> N >> W;
  arr.resize(W+2);
  arr[0] = {1,1};
  arr[1] = {N,N};
  for(int i = 2; i < W+2; i++)
    cin >> arr[i].x >> arr[i].y;
  memset(dp, -1, sizeof(dp));
}

int dist(int p1, int p2) {
  return abs(arr[p1].x-arr[p2].x) + abs(arr[p1].y-arr[p2].y);
}

int go(int p1, int p2) {
  if(p1 == W+1 || p2 == W+1) return 0;
  if(dp[p1][p2] != -1) return dp[p1][p2];

  int next = max(p1,p2)+1;
  //move cap1;
  int d1 = go(next, p2) + dist(p1, next);
  //move cap2;
  int d2 = go(p1, next) + dist(p2, next);
  if(d1 < d2) {
    track[p1][p2] = {next, p2,1};
    return dp[p1][p2] = d1;
  } else {
    track[p1][p2] = {p1, next,2};
    return dp[p1][p2] = d2;
  }
}

int main() {
  fillInput();
  cout << go(0, 1) << "\n";
  int p1 = 0, p2 = 1;
  while(p1 != W+1 && p2 != W+1) {
    cout << track[p1][p2].v << "\n";
    int np1 = track[p1][p2].p1;
    int np2 = track[p1][p2].p2;
    p1 = np1, p2 = np2;
  }
}