[일반] 쉬운 문제 질문좀요

[익명(49.163)]

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

분명 걍 작은것 부터 합치면 되겠지하고 그냥 pq쓰면 답 나옵니다

근데 증명을 안하고해서 잘 모르겠는데

왜 작은 것 부터 합치면 답이 나오는 거죠?

새로더하는 수 + 합해야하는 특정 카드묶음 크기 이므로 새로 더하는 수를 최소화해야한다는 이런 느낌은 있는데 찝찝해요 

[익명(223.63)]

큰 숫자를 여러 번 합치기 vs. 작은 숫자를 여러 번 합치기 뭐 고를래

[익명(122.32)]

카드 묶음을 비교할 때 이전에 합친 2개 카드 묶음의 카드 갯수의 합이 이번에 비교하는 카드 갯수 중 일부가 됨

[익명(122.32)]

따라서 N개의 카드 묶음을 비교할 때 최종 비교 횟수에서 처음으로 합친 카드 묶음은 (N-1)번 포함되고, 2번째로 합친 카드 묶음은 (N-2)번, 3번째로 합친 카드 묶음은 (N-3)번··· 이렇게 가산됨. 최종 더미에 빨리 합치면 빨리 합칠수록 최종 비교 횟수에 많이 중복되어 계산되니까 빨리 합치는 카드 묶음의 카드 개수는 가능한 작은 것이 좋음

[익명(49.168)]

1, 2, 3, 4 를 (1, 2) (3, 4) (3, 7) 처럼 합치면 처음에 합친카드 묶음이 2번만 포함되지 않음?

[익명(122.32)]

어 그러게 ㅅㅂ 반례가 튀어나오네