Fix Wiring
문제
(GPT 번역)
당신은 우주선 ‘더 스켈드(The Skeld)’에서 다른 승무원들과 함께 있습니다.
중앙 전력 시스템을 점검하던 중, 핵심 배선 설치의 한 부분이 훼손된 것을 발견했습니다.
엔진 고장을 막으려면 설치를 신속히 복구해야 합니다.
이 설치는 N개의 노드와 M개의 전선으로 이루어져 있으며,
M은 N개의 노드 쌍을 모두 연결했을 때의 개수, 즉 N(N-1)/2입니다.
서로 다른 모든 노드 쌍이 하나의 전선으로 연결되어 있습니다.
원래는 각 전선마다 정확히 하나의 태그가 붙어 있었고, 각 태그에는 양의 정수가 적혀 있습니다.
서로 다른 태그라도 값이 같을 수 있습니다.
하지만 사보타주로 인해 모든 태그가 전선에서 떨어져 바닥에 흩어졌고,
다행히 당신은 태그 M개를 전부 주워 모았습니다.
이제 설치를 복구하려면 모든 태그를 전선에 다시 붙이는 작업을 두 번 수행해 재부팅 절차를 완료해야 합니다.
모든 전선에 태그가 붙어 있는 설치에 대해, 설치의 비용을 “최소 신장 트리의 비용”으로 정의합니다.
즉, 주어진 전선들 중 일부만 사용해 모든 노드가 서로 연결되도록 할 때 드는 최소 비용을 말합니다.
여기서 전선 집합의 비용은 그 집합에 포함된 전선들에 붙은 태그 값의 합입니다.
재부팅 절차는 두 단계로 진행됩니다.
먼저 태그들을 전선에 붙여 설치의 비용이 최소가 되도록 합니다.
그 다음, 모든 태그를 떼어낸 뒤 다시 붙이되 설치의 비용이 최대가 되도록 합니다.
각 설치의 비용(최소일 때와 최대일 때)을 구하세요.
입력
첫 줄에 노드의 개수 N이 주어집니다. (2 이상 100 이하)
둘째 줄에 태그 값 M개 C1, C2, …, CM이 주어집니다. 여기서 M은 N(N-1)/2이고,
각 Ci는 1 이상 20억 이하의 정수입니다.
출력
한 줄에 두 정수를 출력합니다. 첫 번째는 설치 비용의 가능한 최소값, 두 번째는 가능한 최대값입니다.
풀이
우선 최소 비용은 각각의 노드를 연결하는 간선을 작은 비용순으로 적으면 되므로 비용을 정렬 후 앞에서부터 넣는다.
최대값은 n번째 연결을 할 때 n-1번째의 모든 간선에 작은 순으로 값들을 채우고 남은 다음 값을 적어주는 것이다.
그러면 정렬이 된 비용을 기준으로 n번째 연결을 할 때 n(n-1)/2번째 값을 넣는것이 최대임을 알 수 있다.
구현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
bool flag = 0;
long long a, b, c, d;
long long n, m, t, k = 0;
long long ans = 0;
cin >> n;
vector<ll> v(n*(n-1)/2);
for(int i=0;i<n*(n-1)/2;i++){
cin>>v[i];
}
sort(v.begin(), v.end());
ll mi=0;
ll ma=0;
for(int i=0;i<n-1;i++){ // 무조건 작은거로 연결하고
mi+=v[i];
}
int tt=0;
for(int i=0;i<n-1;i++){ // 각자 최소로 채우며 하나씩 1,3,6,10,15 ...
tt+=i;
ma+=v[tt];
}
cout << mi << ' ' << ma;
return 0;
}