이번 문제는 백준의 실버 2 문제 체인 문제이다.
생각하다보니 문제가 생각보다 어려워, 생각을 정리해보기로 했다.
문제를 차근차근 다시 읽어보자.
체인의 갯수가 주어지며, 각 체인의 길이도 주어진다.
이 때 최소한의 고리를 열어 체인을 하나로 연결하라고 한다.
체인은 최대 50만개가 주어지며, 길이는 최대 100만이다.
이런 경우, 완전 탐색은 직관적으로 불가능 함을 알 수 있다.
정렬과 그리디
그럼 이 문제는 어떻게 풀 수 있을까?
먼저, 고리를 연결할 수 있는 방법은 아래의 두 가지라고 생각한다.
- 고리를 해체하여 해체된 고리로 다른 체인끼리 연결하기
- 각 체인의 연결 부분을 그냥 연결하기
1번 방법의 경우는 예를 들어, 4 3 5 7 9의 체인이 주어질 때
길이 3의 체인을 모두 풀어 4 5 7 9를 연결시킬 수가 있다.
2번 방법의 경우는 4 5 7 9의 경우를 생각해보자.
길이 4의 체인을 모두 풀면 4 5 7 9를 연결하고 고리가 남는다.
그럼 남은 고리도 열어서 연결해야 하므로, 4의 비용이 든다.
하지만 그냥 연결 부위만 열어 연결하면, 3으로 해결이 가능하다.
따라서, 어떤 고리를 모두 풀어서 모두 사용할 수 있는 경우가 아니면?
그냥 연결 부위를 연결하는 쪽이 훨씬 비용이 저렴하다.
또한, 풀 고리를 최소화 하기 위해 길이가 짧은 체인부터 푸는 것이 좋다.
즉, 이 문제는 정렬을 이용한 그리디 문제가 되었다.
체인 길이를 오름차순으로 정렬하여 짧은 체인부터 풀어서 써보도록 한다.
전체 구현 코드는 아래와 같다.
int chain_num = num - 1, answer = 0;
// 연결해야 할 연결 부분의 수
for (int i = 0; i < chains.size(); i++) {
if (chain_num >= chains[i]) {
// 연결해야할 부분이 가장 짧은 체인보다 많으면
// 모두 사용할 수 있음
chain_num -= 1; // 가장 짧은 고리 제외
chain_num -= chains[i];
answer += chains[i];
}
else {
answer += chain_num;
chain_num = 0;
}
if (chain_num <= 0)
break;
}코드를 간단히 설명해보자면,
연결해야 할 부분을 먼저 선언한다. 체인 수 - 1
연결해야 할 부분이 가장 짧은 길이의 체인보다 길면?
해당 체인을 모두 사용할 수 있으므로, 해당 체인을 푼다.
체인을 풀어 연결함은 연결 부분 수 - 체인 길이로 표현한다.
해당 과정을 반복하다, 연결해야 할 부분이 체인보다 짧아지면?
그 때 바로 남은 연결 부위를 연결하도록 하면 된다.