풀이
데스크립션이 이상해서 한참 고민했다 (…)
고리로 이루어진 체인들이 여럿 주어진다.
고리를 최소한으로 사용해서 모든 체인들을 일렬로 연결하고 싶다.
한 고리에는 최대 두 개의 다른 고리(체인)만 연결할 수 있다.
그리디하게 생각해보자!
체인의 수가 작아지면 필요한 고리의 수도 작아진다.
그리고 체인을 모두 고리로 분해하면 체인의 개수가 하나 줄어든다.!
길이가 가장 짧은 체인의 고리부터 사용하면 된다!
같은 양의 고리를 사용하더라도
길이가 짧은 것부터 사용해야 체인의 수를 조금이나마 더 줄일 수 있다.
코드
#include <stdio.h>
#include <algorithm>
int n, s, a[500000];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
std::sort(a, a + n);
for (int i = 0; i < n; i++) {
int cnt = n - i - 1;
s += a[i];
if (s >= cnt) {
printf("%d", cnt);
break;
}
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이