1715. 카드 정렬하기

오랜만에 골드 탐험 ㅎㅎ

1715번: 카드 정렬하기

---

크기가 각각 $a$와 $b$인 카드 묶음을 합치려면 카드를 $a+b$번 비교해야 한다. 카드 묶음의 크기가 주어질 때, 카드 묶음을 하나로 합치려면 카드를 최소 몇 번 비교해야 하는지 구해 보자.

직접 해 보기

크기가 각각 $a$, $b$, $c$인 세 개의 카드 묶음을 합쳐 보자. 먼저 $a$와 $b$를 합치고, 그 후에 $c$를 합친다면 비교 횟수는 몇 번인가?

 

일단 $N$개의 카드 묶음을 하나로 합치려면 묶음을 $N-1$번 합쳐야 한다. 카드 묶음을 합치는 순서에 따라 비교하는 횟수가 달라진다는데, 한번 확인해 보자.

 

$a$와 $b$를 합치는 데 $a+b$번의 비교가 필요하다. 이제 크기가 각각 $a+b$와 $c$인 카드 묶음을 합치려면 $a+b+c$번의 비교가 필요하다. 비교 횟수를 합하면 총 $2a+2b+c$번의 비교가 필요하다. 만약 $a$와 $c$를 먼저 합쳤다면 최종 비교 횟수는 $2a+2c+b$이다. 

 

식을 잘 보니, 먼저 합한 숫자가 제일 많이 더해짐을 알 수 있다. 따라서 가장 작은 묶음을 먼저 합쳐야 비교 횟수를 최소화할 수 있다. 카드 묶음이 하나 남을 때까지 가장 작은 카드 묶음 두 개를 합치고, 그 때의 비교 횟수를 모두 합한 값이 정답이다.

---