[TIL] 99클럽 코테 스터디 18일차 TIL + 백준 2212 센서

 

문제 풀이

 

문제 탐색하기

오늘 문제는 문제를 여러번 읽어도 이해하기가 어려운 문제였습니다.

첫번째 예제를 바탕으로 이해해보도록 하겠습니다.

 

• 센서의 개수 : 6개
• 송신탑의 개수 : 2개
• 센서의 위치 : [1, 3, 6, 6, 7, 9]

 

 

도로 위의 센서의 위치를 나타내면 위 그림과 같습니다. 여기서 각 센서에서 집중국으로 가는 거리의 합이 최소가 되도록 집중국을 위치시켜야합니다. 집중국으로 가는 거리의 합이 최소가 되도록 하려면 위 그림과 같습니다. 집중국의 개수 만큼 분리가 된다고 하면 2개의 그룹으로 분리된다는 것을 알 수 있습니다. 

 

 

이 그림에서 보면 결국 집중국으로 인해 센서 간 가장 거리가 긴 3과 6의 사이를 기점으로 분리가 되었기때문에 가장 긴 길이인 3은 답을 구할때 사용하지 않습니다. 집중국의 수신 가능 길이의 합은 2 + 1 + 2 = 5가 됩니다. 집중국의 개수인 K-1 만큼 긴 거리의 차를 제외하고 합을 구하면 된다는 것을 알 수 있습니다.

 

따라서 센서 간의 거리를 저장하는 배열을 선언하고 그 배열에서 가장 긴 길이 K-1개를 제외한 나머지를 더한 값을 정답으로 출력하면 되는 문제입니다.

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int[] sensor = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            sensor[i] = Integer.parseInt(st.nextToken());
        }

        // 1. 센서 정렬
        Arrays.sort(sensor);

        // 2. 각 센서 간의 거리 차이 배열에 저장하기
        int[] diff = new int[N-1];
        for(int i=0; i<diff.length; i++){
            diff[i] = sensor[i+1] - sensor[i];
        }
        Arrays.sort(diff);

        // 3. K개의 집중국이 지어진다는 것은 센서를 K구역으로 나눈다는 뜻이며
        //      K구역은 K-1개의 거리로 나누어져 있다.
        //      따라서 가장 거리가 긴 K-1개를 제외한 거리들을 더해주면 최소 거리의 합을 구할 수 있다.
        int result = 0;
        for(int i=0; i<diff.length-(K-1); i++){
            result+=diff[i];
        }

        // 출력
        System.out.println(result);
    }
}

 

 

오늘의 회고

오늘 문제는 아무리 문제를 읽어봐도 이해하기가 어려웠습니다. 결국 구글의 도움을 받아서 풀 수 있었는데 참고하여 풀면서도 이해가 잘 가지 않았습니다. 문제를 확실히 이해하고 푸는 것과 이해한 것을 설명하는 것 모두 쉬운일이 아니라는 것을 알 수 있었고 문제에 대한 아이디어가 잘 떠오르지 않았던 문제였습니다. 많은 문제를 풀어서 이런 문제를 접했을 때 좀 더 빠르게 접근할 수 있게 노력해야할 것 같습니다ㅎㅎ..