문제

출처 : https://www.algospot.com/judge/problem/read/STRJOIN

프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자열의 끝을 지정하는데, 이래서는 문자열의 길이를 쉽게 알 수 있는 방법이 없기 때문에 여러 가지 문제가 발생하게 됩니다.

void strcat(char* dest, const char* src) {
 // dest 의 마지막 위치를 찾는다
 while(*dest) ++dest;
 // src 를 한 글자씩 dest 에 옮겨 붙인다
 while(*src) *(dest++) = *(src++);
 // 문자열의 끝을 알리는 \0 을 추가한다
 *dest = 0;
}

이런 문제 중 하나로 문자열을 조작하는 함수들의 동작 시간이 불필요하게 커진다는 것이 있습니다. 앞에 주어진 함수 strcat() 은 문자열 dest 뒤에 src 를 붙이는 함수인데, 실행 과정에서 반복문을 두 문자열의 길이를 합한 만큼 수행해야 합니다. 이 함수를 사용해 두 개의 문자열을 합치는 비용은 두 문자열의 길이의 합이라고 합시다.

이 함수를 이용해 n 개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶습니다. 순서가 상관 없다는 말은 {al,go,spot} 을 spotalgo 로 합치든 alspotgo 로 합치든 상관 없다는 의미입니다. 그러나 문자열을 합치는 순서에 따라 전체 비용이 달라질 수 있습니다. 예를 들어 먼저 al 과 go 를 합치고 (2+2=4), 이것을 spot 과 합치면 (4+4=8) 총 12 의 비용이 들지만 al 과 spot 을 합치고 (2+4=6) 이것을 다시 go 에 합치면 (6+2=8) 총 14 의 비용이 필요합니다.

n 개의 문자열들의 길이가 주어질 때 필요한 최소 비용을 찾는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 문자열의 수 n (1 <= n <= 100) 이 주어지며, 다음 줄에는 n 개의 정수로 각 문자열의 길이가 주어집니다. 각 문자열의 길이는 1,000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 문자열을 합칠 때 필요한 최소 비용을 출력합니다.

풀이

각 숫자들이 입력으로 주어졌을 때, 합치는 것을 반복하는 과정에서 최소가 되는 답을 찾아야 하는데, 이 경우 어림잡아 현재 숫자목록 중 가장 작은 두 숫자끼리 더하는 것이 답이라는 것을 알 수 있다. 이를 증명하기 위해, 먼저 탐욕적 선택 속성을 증명하는데, 현재 숫자 목록에서 가장 작은 숫자와, 임의의 숫자를 더하는 것으로 가정한다. 이 때, 임의의 숫자를 그 다음으로 가장 작은 숫자로 교체한다면, 이때 더해진 숫자가 계속해서 더해지는 과정을 거칠 때 전체 합이 작아진다. 즉, 가장 작은 두 수가 더해지는 최적해가 존재하고, 최적 부분 구조 또한 남은 문자열에서 항상 최소 비용으로 합치는 것이 이득이기 때문에 성립하므로, 이 알고리즘을 통해 답을 계산할 수 있다.

	PriorityQueue<Integer> p = new PriorityQueue<>();
	for(int j=0;j<n;j++) {
		p.add(sc.nextInt());
		}
	int sum = 0;
	while(p.size()!=1) {
		int temp = 0;
		temp += p.poll()+p.poll();
		sum+= temp;
		p.add(temp);
	}
	if(n==1)
		sum = p.poll();
	System.out.println(sum);

구현 자체는 간단한데, 우선순위 큐를 통해 쉽게 풀 수 있다. 큐의 순서가 유지되는 우선순위큐에서 맨 앞에 있는 가장 작은 두수를 꺼내어 더하는 과정을 반복하여, 이 때 더해진 값들의 합을 출력한다.