백준 2212번: 센서 (Python/Java)

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

2212번: 센서

 

 

 

접근

---

 

어느 한 곳에 집중국이 설치되면 그 주위에 있는 센서들의 자료를 모은다. 현재 설치해야 하는 집중국의 개수를 모두 활용해야 한다. 이 말은 즉, 집중국의 개수만큼 영역을 나누라는 뜻이다. 집중국 개수만큼 구역을 나누어주고, 구역마다 바로 옆 센서와의 거리를 구한 뒤, 해당 거리들의 합을 구하면 된다.

 

예제 1번의 경우를 살펴보자. 위치가 1, 6, 9, 3, 6, 7인 6개의 센서, 그리고 여기에 설치해야 할 2개의 집중국이 주어진다. 이 이야기는 6개의 센서를 2개의 집단으로 묶고 각 집단 내 센서들 사이의 거리를 구하라는 뜻이 된다. 우선 센서들을 순서대로 정렬해준다. sort를 이용하면 1, 3, 6, 6, 7, 9가 나온다. 6이 2 개인 건 신경 쓰지 않아도 된다. 어차피 같은 위치에 있는 센서들 사이의 거리는 0이 나오기 때문에 결과에 영향을 주지 않는다.

 

이제 각 센서들 사이의 거리를 구한다. 1-3 사이의 거리, 3-6 사이의 거리... 이렇게 7-9 사이의 거리까지 구한다. 각 거리는 2, 3, 0, 1, 2가 된다. 여기까지 왔으면 바로 눈에 보일 것이다. 어느 부분을 기준으로 나눠야 센서들 사이의 거리가 가장 짧겠는가? 당연히 센서 사이의 거리가 가장 먼 3을 기준으로 집단을 나눠야 센서 거리의 합이 적게 나올 것이다. 집단별로 센서 사이의 거리 합을 구해야 하는데 3이 아니라 1을 기준으로 나누면 3이 결괏값에 더해지므로 해당 결과는 최솟값이 될 수 없기 때문이다. 이제 이를 구현만 하면 된다.

 

센서들 사이 거리의 합은 간단하다. 나눠지는 센서 사이 거리는 버리고 나머지를 합하면 된다. 나는 오름차순으로 센서 사이의 거리 배열을 정렬해준 뒤, 배열 뒤에서부터 나눠야 하는 집중국에서 1을 뺀 만큼 제외하고 나머지 값들을 더하는 방식을 통해 구현했다.

 

 

 

풀이

---

Python

sensorNum = int(input())
centerNum = int(input())

firstLine = (input()).split()

sensorList = []
for i in range(sensorNum):
    sensorList.append(int(firstLine[i]))
sensorList.sort()

lengthList = []
for i in range(1, len(sensorList)):
    lengthList.append((sensorList[i] - sensorList[(i-1)]))
lengthList.sort()

result = 0
for i in range((len(lengthList)-(centerNum-1))):
    result += lengthList[i]

print(result)

 

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int sensorNum = Integer.parseInt(scan.nextLine());
        int centerNum = Integer.parseInt(scan.nextLine());
        
        String[] firstLine = (scan.nextLine()).split(" ");

        ArrayList<Integer> sensorList = new ArrayList<>();
        for(int i = 0 ; i < sensorNum ; i++){
            sensorList.add(Integer.parseInt(firstLine[i]));
        }
        Collections.sort(sensorList);

        int[] lengthList = new int[(sensorList.size()-1)];
        for(int i = 1 ; i < sensorList.size() ; i++){
            lengthList[(i-1)] = (sensorList.get(i) - sensorList.get(i-1));
        }
        Arrays.sort(lengthList);

        int result = 0;
        for(int i = 0 ; i < (lengthList.length - (centerNum-1)) ; i++){
            result += lengthList[i];
        }

        System.out.println(result);

    }

}

 

 

 

후기

---

처음 문제를 풀 때, 거리가 중복인 값들은 제외하려고 했다. 그러다 보니 코드도 몇 줄 더 추가되고 수행하는 연산이 훨씬 많아졌다. 나중에 되어서야 중복인 값들을 결괏값에 영향을 주지 않기 때문에(어차피 중복인 값들 사이의 거리는 0으로 연산되기 때문에) 굳이 제외할 필요가 없다는 걸 깨닫고 현재 코드로 수정했다. 알고리즘을 풀 때 그리고 프로젝트할 때에 필요 없는 연산을 굳이 고생스럽게 하는 경우가 있다. 이런 부분을 조금 더 신경 써야겠다고 생각했다.

 

오늘은 비교적 시간이 많은 주말이라 난이도를 높여서 풀어봤다. 백준 기준으로 골드 5 난이도의 문제를 풀었는데, 그래도 나름 다른 알고리즘을 통해 골드 3 난이도를 풀다와서인지 아니면 그냥 이 문제가 쉬웠던 건지 모르겠지만 어쨌든 생각보다 쉽게 풀 수 있었다. 이 정도라면 내 계획보다 더 난이도를 높여봐도 괜찮을 것 같다.