[알고스팟/ALGOSPOT] 3. STRJOIN

 

 

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

알고스팟 제 3번째 문제는 STRJOIN이라는 문제입니다.

N개의 문자열을 순서와 상관없이 합쳐서 한 개의 문을 만들 때 가장 적은 비용을 구하라는

문제가 됩니다.

이 문제를 생각해보면 항상 제일 작은 문자열끼리 서로 결합을 시키고 또 그다음 작은

문자열끼리 결합을 시켜야 합니다. 그래야 가장 작은 비용으로 결합을 시킬 수 있습니다.

 

그래서

1. N개의 문자열 길이를 오름차순 정렬을 한다.

2. 가장 작은 2개의 문자열을 결합시켜 문자열 길이를 갱신한다.

3. 나머지 N-1개의 문자열 길이를 오름차순 정렬을 한다.

4. 2~3번 과정을 반복하여 마지막 비용 값을 출력한다.

이런 과정이 되겠습니다.

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