코드에서 놓치고 있는 부분이 있습니다
문제의 알고리즘 보기에서 '우선순위 큐' 가 표기된 이유가 있지요
문제의 조건에 따라 최소한의 비교 횟수를 구해야 하므로
카드를 합치고 나서도 가장 수가 적은 카드 뭉치 2개를 비교해야 합니다
안 그러면 큰 수가 여러 번 더해져서 최소한의 수가 도출될 수 없습니다
가령 예를 들어,
30 40 50 60 의 카드 뭉치가 있다고 하면
효율적인 비교(횟수 합계 : sum)는
30 + 40 = 70 # (sum == 70)
50 + 60 = 110 # (sum == 180)
70 + 110 = 180 # (sum == 360)
에 따라 총 360 번의 비교를 수행합니다
하지만 위 코드처럼 자료구조나 추가적인 정렬 등이 없이 순차대로 진행하면
30 x 3 + 40 x 3 + 50 x 2 + 60 x 1 이 됩니다
즉,
30 + 40 = 70 # (sum == 70)
70 + 50 = 120 # (sum == 190)
120 + 60 = 180 # (sum == 370)
이 되므로 10이 더 큰, 잘못된 결과값이 나오게 됩니다
도움이 되셨으면 좋겠네요 :)
llisyn 1년 전
틀렸다고 나오는데 어디서 틀렸는지를 모르겠습니다ㅠㅠ
주어진 문제 뿐만이 아니라 다른 경우들에도 다 맞는다고 생각하는데;;
형님들의 조언 부탁드립니다ㅠㅠ