[백준 코딩테스트] 백준 2212번 센서

내 풀이

고속도로 위에 n개의 센서를 설치한 후 최대 k개의 집중국을 세울 수 있다는게 중점이다.
이 때 수신 가능 영역 길이의 합이 최소가 되어야 한다.
우리는 입력받은 k개의 센서를 오름차순으로 정렬해준 뒤, 각 센서 사이의 거리를 계산한 뒤 오름차순으로 정렬해준다.
이때, 두 점 사이의 거리가 가장 먼 곳부터 제외해준다. 집중국의 개수가 k개 라면 단절선은 k-1개가 된다.
오름차순을 한 결과 값을 n-k개 더해주면 이 문제의 결과가 나온다.

이를 도식화해서 보여주면 다음 그림과 같다.

내 코드

JAVA

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 NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int[] num = new int[n];
        int[] diff = new int[n-1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        if(k>=n){
            System.out.println(0);
            return;
        }

        for(int i=0; i<n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(num);

        for(int i=0; i<n-1; i++){
            diff[i] = num[i+1] - num[i];
        }
        
        Arrays.sort(diff);

        int sum = 0;

        for(int i=0; i<n-k; i++){
            sum += diff[i];
        }

        System.out.println(sum);
    }
}

Python

def main():
    # 입력 처리
    n = int(sys.stdin.readline().strip())
    k = int(sys.stdin.readline().strip())
    
    # k가 n보다 크거나 같으면 0 출력 후 종료
    if k >= n:
        print(0)
        return

    # 숫자 입력 및 정렬
    num = list(map(int, sys.stdin.readline().split()))
    num.sort()

    # 차이 계산 및 정렬
    diff = [num[i+1] - num[i] for i in range(n-1)]
    diff.sort()

    # 합계 계산
    sum_diff = sum(diff[:n-k])

    print(sum_diff)

if __name__ == "__main__":
    main()