1715 - 카드 정렬하기

https://www.acmicpc.net/problem/1715

항상 카드의 장수가 가장 작은 두 묶음을 합치는 것이 결과적으로 최소의 비교 횟수이다.

대체 왜..?

라고 생각할수있다. "왠지 그러는 게 맞는 것 같다"는 말도 안되는 논리(혹은 풀이 도출)로 풀어온 문제가 정말 많았다.
그래서 오늘은 증명을 연습해보려 한다.

카드를 합치는 과정을 설명하기 위해 다음과 같이 정의해보겠다.
$a =$ 가장 작은 수 (i.e. $a$장의 카드 묶음)
$b =$ 두번째로 작은 수
$c = a, b$ 가 아닌 다른 어떤 수

위 정의에 의하면 $a \le b \le c$ 이다. 아래 3가지 경우가 있다.

• $a$와 $c$를 합친 후, 그것을 $b$와 합친다 : $(a+c)+ \{(a+c)+b\}$
• $a$와 $b$를 합친 후, 그것을 $c$와 합친다 : $(a+b)+ \{(a+b)+c\}$
• $b$와 $c$를 합친 후, 그것을 $a$와 합친다 : $(b+c)+ \{(b+c)+a\}$

세 항 모두 중괄호로 둘러싼 부분이 $a+b+c$로 공통이므로 비교하기 위해 생략할 수 있다.

$a+b \le a+c$ 이고, $a+b \le b+c$ 이므로
$(a+b)+ \{(a+b)+c\}$ 가 가장 최소이다.

따라서 가장 작은 두 수를 합치는 것이 항상 최소이다.

증명을 별로 해본적이 없어서 맞는 지 확신이 안 선다.
댓글로 지적해주시면 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int main(){
    int t, N;
    scanf("%d", &N);
    priority_queue<int> q;
    while(N--){
        scanf("%d",&t);
        q.push(-t);
    }
    int r = 0;
    while(q.size()>1){
        int a=0, b=0;
        a = -q.top(); q.pop();
        b = -q.top(); q.pop();
        r += a+b;
        q.push(-a-b);
    }
    printf("%d", r);
    return 0;
}