[1. 문제 설명]
n 개의 문자열들의 길이가 주어질 때,
n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때
필요한 비용의 최소 값
ex)
{al, go, spot} 을 합칠 때
{al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12
[2. 풀이 접근]
한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면
병합되는 문자열들의 총 길이가 전체 비용에 더해진다.
병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다.
위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고
"algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다.
그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 것이 타당해보인다.
=== 정당성 증명
가장 짧은 두개의 문자열을 합치는 최적해가 반드시 있음을 보이도록 한다.
- 문제의 최적해가 가장 짧은 두개의 문자열 a, b 를 서로 처음에 합치지 않는 형태라 가정한다.
- 이 최적해를 변형해서, 항상 a 와 b 를 처음에 합치는 최적해도 존재함을 보이도록 한다.
- [1] 에서 최적해로 정의한 형태에서 a 와 b 가 최초로 합쳐진 시점에서 문자열을 X 라 하자
- 이때, X 이후의 문자열에는 영향을 주지 않는다.
=> X 의 길이는 문자열들의 위치가 바뀌어도 일정하기 때문이다.
=> X 까지 문자열을 합치는데 필요한 비용만 고려하도록 한다. - a 와 b 가 X 에서 몇단계나 떨어져 있나를 비교하도록 한다.
A. 거리가 같은 경우
=> x 와 b 를 바꿔도 답은 변하지 않는다.
B. 거리가 다를 경우
=> a, b 중에 X 에 더 가까운 쪽이 더 먼쪽과 합쳐지도록 옮긴다.
=> x 가 병합되는 횟수는 더 줄어들고, b 가 병합되는 횟수는 그만큼 늘어난다.
=> 그러나 x 의 길이는 b 보다 항상 더 크거나 같기 때문에, 바꾼 해는 결과적으로 항상 이득이거나, 같게 된다.
=== 최적 부분구조
두 문자열을 합치고 나면, 남은 문자열들 역시 항상 최소 비용으로 합쳐야 전체가 최소가 된다.
[3. 코드]
'알고리즘 > 이론' 카테고리의 다른 글
05. 조합 탐색 (0) | 2022.10.09 |
---|---|
04. 탐욕법 - 예제3 (0) | 2022.10.03 |
04. 탐욕법 - 예제1 (0) | 2022.10.03 |
04. 탐욕법 (0) | 2022.10.03 |
03. 동적계획법 - 예제4 (0) | 2022.10.02 |