체인( BOJ 2785 )

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

2785번: 체인

 

문제 파악하기

N개의 체인을 하나로 연결하기 위해 필요한 고리의 최소 개수를 구하는 문제입니다. 각각의 고리는 분리되어 다른 체인들을 연결할 수 있으며, 최대 2개의 체인을 연결할 수 있습니다. 문제를 분석해보면 결국 체인, 즉 숫자와 숫자 사이를 연결하기 위해 사용되는 고리의 개수를 구하는 문제입니다. 따라서, 연결에 사용되는 고리의 개수를 줄이기 위해서는 하나의 체인을 전부 다른 체인을 연결하는 고리로 사용하면 됩니다. 이는  만약 체인이 [ 4 3 5 7 9 ]가 있다면, 가장 작은 고리를 가진 두 번째 체인(3)을 분리하여 다른 체인들을 연결하면 3개의 고리만을 사용하여 5개의 체인을 모두 하나로 연결할 수 있습니다. ( [예시] 4 - 5 - 7 - 9 ) 이를 효율적으로 만드는 알고리즘을 알아봅시다.

 

문제 해결하기

결국 문제는 가장 작은 개수의 고리를 가진 체인부터 하나씩 탐색하는 문제로 바뀌며, 정렬을 사용하면 효율적으로 탐색을 할 수 있습니다. 정렬하여 가장 작은 값을 찾은 다음, 현재 체인의 고리로 남아있는 모든 체인을 연결할 수 없다면 결괏값에 누적하여 넘어갑니다. 만약 현재 탐색하는 체인의 고리를 모두 사용하면 남은 체인을 전부 연결할 수 있다면 지금까지 사용한 고리와 방금 확인한 체인의 고리까지 전부 더해서 결과를 출력하면 됩니다. 반대로 현재 탐색하는 체인의 고리 중 일부분을 사용해야 한다면 (지금까지 남은 체인의 개수 - 1)개를 출력하면 됩니다. 이는 이전에 얼마나 많은 고리를 사용했든 지금 확인한 체인의 고리 중 일부분을 사용해서 남은 모든 체인을 연결해야 하기에 별도의 계산 없이 남은 체인의 개수를 사용하면 확인할 수 있습니다.

 

문제를 해결하기 위해서는 지금까지 남은 체인 중 가장 고리의 개수가 적은 체인부터 확인해야 합니다. 정렬을 사용할 수도 있지만, 입력되는 값을 바로 정렬해주는 우선순위 큐를 사용해서 해결할 수도 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int N, t;
priority_queue< int, vector< int >, greater< int > > q;
 
int cur, ret;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
        q.push(t);
    }
    
    while(ret<q.size()-1) {
        cur = q.top();
        
        if(ret+cur<=q.size()-1) ret += cur;
        else ret = (int)q.size()-1;
        
        q.pop();
    }
    
    printf("%d", ret);
    
}
/*
6
1 2 10 10 10 10
ans: 3
 
4
1 10 10 10
ans: 2
 */
 

후기

문제에서 요구하는 조건이 조금 이해하기 어려웠으나 문제 자체는 나름 재미있는 문제입니다. 입력된 값의 개수가 크기 때문에 내장된 sort 함수를 사용하거나 효율적인 자료구조 또는 정렬 알고리즘을 사용해 최솟값을 찾을 수 있다면 문제를 어렵지 않게 해결할 수 있습니다. 정렬 혹은 우선순위 큐를 연습하는 사람에게 추천할 만한 문제라고 생각합니다.