백준 2785번 체인 C++

https://www.acmicpc.net/problem/2785

2785번: 체인

 

고리의 수가 적은 체인부터 분해하여 연결해야 한다.

 

1. 정렬을 한다.

 

2. 연결해야 하는 체인의 수가 제일 작은 체인의 고리의 수와 같으면 제일 작은 체인을 분해해서 연결하면 딱 떨어진다.

3. 연결해야 하는 체인의 수가 제일 작은 체인의 고리의 수보다 크다면 제일 작은 체인을 분해하고 다음 체인까지도 고려해야 한다.

4. 연결해야 하는 체인의 수가 제일 작은 체인의 고리의 수보다 작다면 제일 작은 체인을 분해하면 모든 체인을 연결할 수 있지만 자기의 체인이 남기때문에 1을 더해줘야한다.

 

2~4 검사 반복

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long; 

int n;
vector<int> v;

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

    cin >> n;
    v = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int ans = 0;
    int idx = 0;
    int cnt = v.size() - 2;
    while (true) {
        if (cnt == v[idx]) {
            ans += v[idx];
            break;
        }
        else if (cnt > v[idx]) {
            ans += v[idx];
            cnt -= v[idx] + 1;
            idx++;
        }
        else {
            ans += cnt + 1;
            break;
        }
    }
    cout << ans;
}