경찰차
-
[문제해결을 위한 창의적 알고리즘] 경찰차 2 (고급, p170)알고리즘 2017. 2. 4. 21:33
앞선 포스트에서 가장 쉬운 완전탐색 방법으로 해결하는 코드를 소개한 적이 있다. 이 방법보다 보다 효율적인 방법으로 메모이제이션을 활용한 코드를 소개하고자 한다. import java.util.Scanner; public class PatrolCarSol174 { public static int[][] E = new int[1010][2]; public static int n, m, ans =987654321; public static int[][] DT=new int[1100][1100]; 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 ..
-
[문제해결을 위한 창의적 알고리즘] 경찰차 1 (고급 p.170)알고리즘 2016. 12. 16. 18:14
이 문제는 중급에서도 다뤄진 적이 있는 문제이다. 해설에서 설명하고 있는 내용은 경찰차 두대의 위치를 다른 사건들의 지점과 함께 배열에 저장한 다음, 두개의 포인터를 가지고 두대의 경찰차를 다음 포지션으로 이동시켜가면서 거리의 합을 구한다. 모든 사건이 다 처리되었을 때, 이동거리가 최소가 되도록 하면 된다. 이 포스트에서는 먼저 다이내믹 프로그래밍을 이용하지 않은 경우의 솔루션을 보기로 한다. import java.util.Scanner; public class PatrolCarSol173 { // 사건의 개수가 최대 1000개 이므로 1002까지만 있으면 된다 public static int[][] E = new int[1002][2]; public static int n, m; public stat..