[백준/Baekjoon] 2785 체인 C++ :: Greedy

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

2785번: 체인

 

 

---

 

 

1. Logic

- 부분 문제로 나눠서 생각을 해봤을 때 

1. 원래 있는 체인을 사용해서 연결하는 경우

2. 서로 끝부분끼리 연결하는 경우

이렇게 두가지로 나누어진다고 생각했다.

 

원래 있는 체인을 사용하는 경우 연결하는 부분의 갯수가 체인의 길이를 넘게 되면 항상 비효율적으로 사용하기 때문에 사용하는 기존 체일을 제외한 갯수와 사용하는 체인의 갯수가 똑같아야만 한다.

 

서로 끝부분끼리 연결하는 경우 갯수를 오름차순 정렬한 상태로 제일 갯수가 적은 것 부터 사용하며 사용할 때마다 1개씩 빼주고 0이 되게되면 뒤에서부터 하나씩 밀어나온다.

 

#include<bits/stdc++.h>

using namespace std;

vector<int> vec;

int main () {
    int n;
    int cnt = 0;
    
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        vec.push_back(a);
    }

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

    while(vec.size() > 1) {
        vec[vec.size() - 2] += vec[vec.size() - 1];
        vec[0]--;
        cnt++;

        vec.pop_back();


        if(vec[0] == 0) {
            for(int i = 0; i < vec.size(); i++) {
                vec[i] = vec[i + 1];
            }
            vec.pop_back();
        }
    }

    cout << cnt;
}