백준 2785 - 체인

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 체인의 길이가 주어진다.

N개의 체인의 고리를 임의로 벌려 연결할 수 있다.

고리를 벌려 모든 체인을 연결하려면 최소한 몇 개의 고리를 벌려야 하는지 구해야 한다.

 

해당 문제는 문제를 이해하는데 어려움이 있을 수 있다.

내가 헷갈렸던 부분은 각 체인이 원래의 길이를 유지해야 하는 줄 알았다.

하지만, 문제에서 각 체인을 분리할 수 있다는 지문을 보면 알 수 있듯이 고리를 하나씩 떼어내도 괜찮다.

이를 생각하고 문제를 풀면 다음과 같이 풀 수 있다.

 

길이가 가장 짧은 체인에서 하나의 고리씩 떼어내어 길이가 가장 긴 두개의 체인을 연결한다.

이를 체인이 1개로 연결되기까지 반복한다.

만약, 길이가 가장 짧은 체인의 고리르 모두 떼어내어 남아있지 않다면 제외시킨다.

즉, 길이순으로 정렬한 뒤, 0번 인덱스의 체인의 길이를 하나씩 줄여가며 제일 뒤에 2개의 체인을 하나로 합친다.

int ans = 0;
while (chains.size() != 1)
{
    chains[0]--;
    ans++;

    chains[chains.size() - 2] += chains[chains.size() - 1];
    chains.pop_back();

    if (chains[0] == 0) chains.pop_front();
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N;

    deque<int> chains(N);
    for (int i = 0; i < N; i++)
    {
        cin >> chains[i];
    }

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

    int ans = 0;
    while (chains.size() != 1)
    {
        chains[0]--;
        ans++;

        chains[chains.size() - 2] += chains[chains.size() - 1];
        chains.pop_back();

        if (chains[0] == 0) chains.pop_front();
    }

    cout << ans;

    return 0;
}

---