문제 출처

1. 문제설명

• N개의 체인이 주어진다.
• 다음 N개의 줄에는 각 체인의 개수를 나타내는 양의 정수가 주어진다.
• 하나의 긴 체인으로 모두 묶기 위해 열고 닫아야할 고리 수를 찾아라.

2. 알고리즘 설계

• 최대한 적은 고리를 이용해 하나로 만들어야 한다.
  • 체인의 개수에 따라 정렬
• 가장 개수가 적은 고리를 하나 풀어서 뒤에 두개를 이어주고 더한다.
• 만약 가장 개수가 적은 고리가 0개가 되면 그 다음 고리를 사용한다.

3. 로직

• vector의 front(), back()을 사용
  • 각각 가장 적은 체인의 개수, 가장 많은 체인의 개수

• 예시

  5
  4 3 5 7 9
  
  3 4 5 7 9  // 정렬
  
  2 4 5 16  // 가장 적은 고리 하나 제거하고, 뒤에 두개의 값 잇기
  1 4 21  // 상기 주석과 동일
  25  // 하나가 되었으므로 종료
  

4. 전체 코드

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

int main(void) 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

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

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

	int start = 0, end = v.size() - 1;
	int ans = 0;

	while (start < end) {
		int back = v[end];
		int front = v[start];

		if (v[start] == 0) {
			start++;
			continue;
		}

		v[--end] += back;
		v[start]--;
		ans++;
	}

	cout << ans;
}