[백준] 센서

[hye-on]

🔗 센서

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//10:25
int n, k;
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    cin >> k;
    vector<int>v;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    sort(v.begin(), v.end());

    for (int i = 1; i < n; i++) {
        v[i - 1] = v[i] - v[i - 1];
    }
    v[n - 1] = 0;


    sort(v.begin(), v.end());
    int ans = 0;

    //2 3 0 1 2
    // 0 1 2 2 3 - 3을 뺌
    for (int i = 0; i < n - k+1; i++)
        ans += v[i];

    cout << ans;
    return 0;
}

코멘트

- 처음엔 어려웠는데 뺄 거리를 생각하니까 좀 간단해진 것 같습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

/**
 * 11:03
 */
public class Main
{
    /**
     * 1 3 66 7 9
     * 3 6 7 8 10 12 14 15 18 20  
     */
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	   
	    int n = Integer.parseInt(bf.readLine());
	    int k = Integer.parseInt(bf.readLine());
	    int[] sensors = new int[n];
	    
	    StringTokenizer st = new StringTokenizer(bf.readLine()); 
	    for(int i = 0; i < n; ++i) {
	        sensors[i] = Integer.parseInt(st.nextToken());
	    }
	    
	    Arrays.sort(sensors);
	    
	    int[] gaps = new int[n-1];
	    for(int i = 1; i < n; ++i) {
	        gaps[i-1] = sensors[i] - sensors[i-1];
	    }
	    
	    Arrays.sort(gaps);
	    
	     int total = sensors[n-1] - sensors[0];
	    for(int i = n - 2; i >= 0; --i) {
	        if(k == 1) break;
	        total -= gaps[i];
	        k--;
	    }
	    
	    System.out.println(total);
	}
}

코멘트

- 그리디로 풀었습니다! (전체 센서 범위에서 K-1개의 갭을 뺀다)