[SWEA] 6855 신도시 전기 연결하기

문제

SWEA 6855 : 신도시 전기 연결하기

SW Expert Academy

접근

N채의 집들 사이의 거리를 구해 배열에 저장한 뒤 내림차순 정렬해 주었다. 그러면 거리가 멀리 떨어져서 설치해야 할 전선 길이가 가장 긴 순서대로 정렬이 될 텐데, 이때 전선을 가장 적게 써야 하므로 발전소를 이용해 가장 멀리 떨어진 집을 잇지 않고 각각 발전소를 따로 세워주면 된다. (이는 설치할 예정인 발전소의 개수는 두 개 이상이어야 하며, 발전소 - 1 개 만큼의 집 사이의 거리를 상쇄할 수 있다.)

 

코드

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

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k, arr[100010], answer = 0;
        cin >> n >> k;
        for (int j = 0; j < n; j++) {
            cin >> arr[j];
        }
        vector<int> v;
        for (int j = 1; j < n; j++) {
            v.push_back(arr[j] - arr[j - 1]);
        }
        sort(v.begin(), v.end(), greater<int>());
        for (int j = k - 1; j < v.size(); j++) {
            answer += v[j];
        }
        cout<<"#"<<i + 1<<" "<<answer<<"\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study