항상 카드의 장수가 가장 작은 두 묶음을 합치는 것이 결과적으로 최소의 비교 횟수이다.
대체 왜..?라고 생각할수있다. "왠지 그러는 게 맞는 것 같다"는 말도 안되는 논리(혹은 풀이 도출)로 풀어온 문제가 정말 많았다.
그래서 오늘은 증명을 연습해보려 한다.
카드를 합치는 과정을 설명하기 위해 다음과 같이 정의해보겠다.
$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\}$ 가 가장 최소이다.
따라서 가장 작은 두 수를 합치는 것이 항상 최소이다.
증명을 별로 해본적이 없어서 맞는 지 확신이 안 선다.
댓글로 지적해주시면 감사하겠습니다.
