[백준] 2785번 - 체인

문제 >

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

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

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

 

입력 >

첫 번째 줄에는 체인의 개수를 나타내는 양의 정수 N (2 ≤ N ≤ 500000)이 주어진다. 두 번째 줄에는 각각의 체인의 길이를 나타내는 N개의 양의 정수 Li(1 ≤ Li ≤ 1000000)가 주어진다.

출력 >

첫째 줄에 필요한 고리의 최소 개수를 출력한다.

 

해결방법 > 

그리디 알고리즘으로 해결

 

가장 짧은 체인으로 고리를 만들어 가장 긴 체인부터 연결하며 체인의 개수가 1이 될 때까지 반복해나간다.

 

입력받은 체인의 길이를 오름차순으로 정렬하고 맨 앞의 체인 길이를 하나씩 줄여가며 맨 뒤의 체인을 연결.

 

3 4 5 7 9

2 4 5 16 

1 4 21 

25

 

 

[C++]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 체인의 길이를 오름차순으로 정렬한 뒤에, 적은 수의 체인부터 고리로 풀어헤치면서 큰 수의 체인을 연결한다.
int main(){
    int n;
    int cnt = 0;
    vector <int> v;

    cin >> n;

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

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

    while(1){
        if(v.size() == 1)
            break;
        
        v[v.size() - 2] += v[v.size() - 1];
        v.pop_back();
        cnt++;
        v[0]--;

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

    cout << cnt;

}

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_2785 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList <Integer> a = new ArrayList();
		int cnt = 0;
		
		for(int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			a.add(tmp);
		}
		
		Collections.sort(a);
		
		while(true) {
			if(a.size() <= 1)
				break;
			a.set(0, a.get(0) - 1);
			a.remove(a.size() - 1);
			if(a.get(0) == 0)
				a.remove(0);
			cnt++;
		}
		System.out.println(cnt);
	}
}

 

문제링크 >

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

2785번: 체인