[백준] 경비원 - 2564

문제설명

www.acmicpc.net/problem/2564

2564번: 경비원

 

기본아이디어

일단 먼저 든 생각은 오른쪽으로 갈지 왼쪽으로 갈지는 한 곳을 구한 뒤에 전체에서 빼면 다른 한쪽으로 가는 거리를 구할 수 있다는 것이었다. 그리고 두번째 든 생각은 case로 다 나눠서 풀면 풀리겠다고 생각이 들었다. 동근이의 현재 위치와 상점의 현재 위치를 비교하면서 진행하면 풀 수 있다고 확신이 들었다.

 

그리고 두번째 풀이, 어차피 모든 위치는 한 지점, 예를들어 제일 위, 왼쪽의 점을 (0, 0)이라고 생각했을 때 모든 상점, 동근이의 위치까지 거리를 구할 수 있다. 그리고 구한 거리끼리의 차이는 결국 두 지점의 거리라고도 할 수 있다. 이런 방식을 선택하면 편하게 동서남북 위치의 값으로 바꿀 수 있고, 동근이의 상대적 거리와의 차이의 절댓값을 씌우면 간단하게 값을 구할 수 있다.

 

구현코드

 public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        StringTokenizer st = new StringTokenizer(input.readLine());
        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
 
        int N = Integer.parseInt(input.readLine());
        int[][] map = new int[N][];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(input.readLine());
            int[] temp = new int[2];
            temp[0] = Integer.parseInt(st.nextToken());
            temp[1] = Integer.parseInt(st.nextToken());
            map[i] = temp;
        }
        st = new StringTokenizer(input.readLine());
        int[] dongGn = new int[2];
        dongGn[0] = Integer.parseInt(st.nextToken());
        dongGn[1] = Integer.parseInt(st.nextToken());
 
        int min_dist = 0;
        int total_dist = 2*width + 2*height;
        int dognGn_dist = cal(dongGn[0], dongGn[1]);
        for(int i = 0; i < N; i++){
            int dist = cal(map[i][0], map[i][1]);
            int diff = Math.abs(dognGn_dist - dist);
            min_dist += Math.min(diff, total_dist-diff);
        }
        System.out.println(min_dist);
    }
    static int width, height;
    static int cal(int loc, int dist){
        switch (loc){
            case 1:
                return dist;
 
            case 2:
                return width + height + width - dist;
 
            case 3:
                return width + height + width + height - dist;
 
            case 4:
                return width + dist;
        }
        return 0;
    }

 

정리, 기억할 내용

1. 손으로 그려보자.

2. 간단하게 풀 수 있을지 생각하자.