[문제해결을 위한 창의적 알고리즘] 경찰차 1 (고급 p.170)

이 문제는 중급에서도 다뤄진 적이 있는 문제이다. 해설에서 설명하고 있는 내용은 경찰차 두대의 위치를 다른 사건들의 지점과 함께 배열에 저장한 다음, 두개의 포인터를 가지고 두대의 경찰차를 다음 포지션으로 이동시켜가면서 거리의 합을 구한다. 모든 사건이 다 처리되었을 때, 이동거리가 최소가 되도록 하면 된다.

이 포스트에서는 먼저 다이내믹 프로그래밍을 이용하지 않은 경우의 솔루션을 보기로 한다.

import java.util.Scanner;

public class PatrolCarSol173 {

// 사건의 개수가 최대 1000개 이므로 1002까지만 있으면 된다

public static int[][] E = new int[1002][2];

public static int n, m;

public static int ans = 0x7fffffff;

public static int min(int a, int b) {

return  a>b? b: a;

}

public static int abs(int a) {

return a > 0 ? a : -a;

}

//경찰차 이동 거리 구하기

public static int dis(int a, int b) {

return abs(E[a][0]-E[b][0])+abs(E[a][1]-E[b][1]);

}

public static int f(int a, int b) {

int next=(a>b?a:b)+1;

if(next>=m+2)

return 0;

return min(f(next, b)+dis(a,next), f(a,next)+dis(b,next));

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

E[0][0]=E[0][1]=1;

E[1][0]=E[1][1]=n;

for (int i = 2; i<m+2; i++) {

E[i][0]=sc.nextInt();

E[i][1]=sc.nextInt();

}

sc.close();

System.out.println(f(0,1));

return;

}

}

*한국정보올림피아드(2003 전국본선 중등부)

Big O(2^n): 다음 사건으로 이동하면서 두대의 경찰차 중 어느 경찰차를 이동시킬 것인지 계산, n은 사건 숫자

Github:  https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/PatrolCarSol173.java

문제해결을 위한 창의적 알고리즘 목록