백준 2785 (C++) 체인

최초 업로드: 2025-03-13 00:05:00

최근 수정 시간: 2025-07-25 10:16:24

카테고리: 백준

# [Silver I] 체인
[문제링크](https://www.acmicpc.net/problem/2785)

## 문제 설명

희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그래서, 체인을 분리하거나 두 체인을 연결하여 하나의 긴 체인으로 만들 수 있다. 희원이는 가능한 한 적은 고리를 열고 닫아서, 모든 체인을 하나의 긴 체인으로 연결하려고 한다.

예를 들어, 희원이가 세 개의 체인을 가지고 있고, 각 체인이 고리 하나로만 이루어져 있다면, 그 중 하나를 열어서 나머지 두 개를 연결하고 닫으면 된다.

체인의 개수와 각각의 체인의 길이가 주어지면, 하나의 긴 체인으로 모든 체인을 묶기 위해 희원이가 열고 닫아야할 최소한의 고리 수를 찾아라.

## 입력

첫 번째 줄에는 체인의 개수를 나타내는 양의 정수 N (2 ≤ N ≤ 500000)이 주어진다. 두 번째 줄에는 각각의 체인의 길이를 나타내는 N개의 양의 정수 Li(1 ≤ Li ≤ 1000000)가 주어진다.

## 출력

첫째 줄에 필요한 고리의 최소 개수를 출력한다.

## 풀이
#### 다양한 길이의 체인들을 하나의 체인으로 합치는 문제입니다.
#### 체인 n개를 연결하는 가장 간단한 방법은 각각의 두 체인의 끝을 연결하여 총 n-1번 시도하는 방법입니다.
#### 하지만 n-1번보다 짧은 임의의 길이의 체인을 분해하여 연결한다면 원래의 방법보다 시도 횟수가 1회 줄어듭니다.
#### 또한 분해하는 체인의 길이를 x라고 하면 분해하기 전보다 체인의 수가 x+1개 줄어듭니다.
#### 시도 횟수를 최소로 하려면, 체인을 최대한 많이 분해하여야 하고, 이는 정렬하여 짧은 길이의 체인부터 분해하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector<int> v(n);
 for(int i=0;i<n;i++) cin >> v[i];
 sort(v.begin(), v.end());

int cnt=n-1, total=n;
 for(int i=0;i<n;i++) { // 작은 체인부터 가능한 동안 분해하여 연결
 if(total-v[i]-1>0) {
 total -= v[i]+1;
 cnt--;
 } else {
 break;
 }
 }
 cout << cnt;
}
```