10.4_문자열 합치기_STRJOIN

문제 설명

 

algospot.com :: STRJOIN

• 두 개의 문자열을 합치는 비용 = 두 문자열 길이의 합
• 문자열을 합치는 순서에 따라 전체 비용이 달라진다.
• (2+2) + (2+2+4) = 12
• (2+4) + (2+4+2) = 14

=> n개의 문자열들의 길이가 주어질 때 필요한 최소 비용을 출력하기

 

 

문제 풀이

문자열을 합치는 최소비용이란

 

예시에서 주어진 문자열의 계산법은

(a+b) + (a+b+c) + ... 으로 이루어진다.

먼저 더해진 문자열들은 뒤의 연산에 계속 사용되므로

짧은 문자열이 먼저 더해지는 것이 이후의 연산결과를 줄일 수 있는 방법이다.

 

계산 과정

 

문자열이 더해지고 나면, 기존 문자열 2개 -> 길이가 늘어난 문자열 1개가 새로 생긴다.

이 문자열을 포함하여 가장 짧은 문자열 두개를 더해가는 과정을 반복하고

그 비용을 출력하였다.

 

문제 풀이 코드

#include <iostream>

using namespace std;

#define MAXN 100

int strlength[MAXN];
int temp[MAXN];

void mergeSort(int startIdx, int endIdx, int mid) {
	int i = startIdx;
	int j = mid + 1;
	int l = startIdx;

	while (i <= mid && j <= endIdx) {
		// 문자열의 길이가 짧은 것을 앞에 배치
		if (strlength[i] < strlength[j])
			temp[l++] = strlength[i++];
		else
			temp[l++] = strlength[j++];
	}

	while (i <= mid)
		temp[l++] = strlength[i++];
	while (j <= endIdx)
		temp[l++] = strlength[j++];

	for (int l = startIdx; l <= endIdx; ++l)
		strlength[l] = temp[l];
}

void sort(int startIdx, int endIdx) {	// 정렬
	if (startIdx >= endIdx) return;
	int mid = (startIdx + endIdx) / 2;

	sort(startIdx, mid);
	sort(mid + 1, endIdx);
	mergeSort(startIdx, endIdx, mid);
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cin >> strlength[i];
		}

		if (n == 1) {
			cout << strlength[0] << endl;
			continue;
		}

		int sum = 0;
		int cnt = n;
		// 더해진 문자열을 포함해 가장 짧은 두 문자열을 더하기
		for (int i = 0; i < n-1; ++i) {
			sort(0, cnt - 1);
			sum += strlength[0] + strlength[1];
			strlength[0] += strlength[1];
			strlength[1] = strlength[--cnt];
		}

		cout << sum << endl;
	}
	return 0;
}