백준 2785번: 체인 - C++ 탐욕(Greedy)알고리즘

 

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

 

 

 

문제를 이해하는데 시간이 좀 걸렸다.

 

주어진 체인들의 고리를 풀어서 연결하여 하나의 긴 체인으로 만들어야 한다.

가장 적은 수의 고리를 사용하려면 가장 짧은 체인의 고리를 풀어 가장 긴 체인들을 묶는데 사용해버리는 것이 유리.

 

가장 짧은 체인부터 사용하게 될 경우 결과적으로 연결해야하는 체인의 수가 줄어들어 더 적은 고리를 사용할 수 있다.

체인을 모두 연결했을 때, 사용하던 체인의 고리가 남아버리는 것은 상관 없다.

 

길이가 각각 7 3 1 8 9 4 인 체인 6개가 입력으로 들어왔을 때,
제일 앞에서부터 순서대로 묶어버리는 경우
길이가 7인 체인의 고리 하나를 사용해 3 1을 묶고,
그 다음 8 체인과, 3과 1이 묶여서 4가 된 체인을 또 연결하고
그 다음 9 체인과 앞에서 연결한 12 체인을 연결하고...
결국 최악의 결과인 고리 5개를 사용하게 된다.
 
반면에 1 3 4 7 8 9 로 정렬하여
제일 짧은 체인으로 긴 체인을 연결하는 경우
1을 사용하여 8과 9를 묶는다.
1은 연결하는데 사용되어 없어지고, 다른 체인들과 연결하지 않아도 된다.
이후 3짜리 체인의 고리를 사용하여 나머지 체인들을 묶는다.
총 3개의 고리만 사용하는 최선의 결과가 나온다.

 

 

 

vector를 사용하려다가 삭제가 빈번하게 일어날 것 같아 deque로 변경했다.

 

입력받은 체인 배열을 정렬하고, 배열이 빌 때까지 제일 짧은 체인을 배열에서 꺼내 그 고리 수 만큼 뒤에서부터 pop 하는 것을 반복하며, 그 횟수를 세어 출력한다.

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
    int chainNum, chainLen, minChain;
    int ringCnt = 0;

    deque<int> chainLengths;

    cin >> chainNum;


    for (int i = 0; i < chainNum; i++) 
    {
        cin >> chainLen;
        chainLengths.emplace_back(chainLen);
    }

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


    minChain = chainLengths.front();
    chainLengths.pop_front();

    while (!chainLengths.empty()) 
    {
        if (minChain <= 0)
        {   
            minChain = chainLengths.front();
            chainLengths.pop_front();
        }
        else
        {
            ++ringCnt;
            --minChain;
            chainLengths.pop_back();
        }     
    }

    cout << ringCnt;

}