https://www.acmicpc.net/status?user_id=gnsdh8616&problem_id=1715&from_mine=1
난이도에 비해 쉬운문제 같다고 느껴졌다.
최소힙을 이용하여 풀면 된다.
처음풀이
for (let i = 0; i < N; i++) {
if (arr[i] > 0) {
pq.insert(arr[i]);
}
}
let sum = 0;
while (pq.size() > 2) {
sum += pq.remove() + pq.remove();
pq.insert(sum);
}
console.log(sum);pq의 사이즈가 3개 이상일때만 반복문을 도는데(맨 처음 요소는 고정 값이므로 쓰이지 않음)
입력 값이 만약 10,20,40이라고 할때(순서는 상관없다),
이진 트리를 생각해보면
최소힙이므로 이렇게 들어가있다.
따라서, 여기서 10,20을 빼서 sum에 넣고 그것을 다시 이진 트리에 삽입하면
이렇게 되고, sum에 다시 (30+40)을 더해서 테스트케이스를 만족한다.
그래서 당연히 맞았는줄 알았는데 틀렸다고 한다.
자세히 보면 마지막엔 100이 아니라 70이 들어가야 한다.
즉, sum을 누적해서 더하는건 맞지만 sum 변수는 매번 더할때 새로 갱신이 되어야 하는 값이다.
따라서,
let total = 0;
while (pq.size() > 2) {
let sum = pq.remove() + pq.remove();
pq.insert(sum);
total += sum;
}
console.log(total);다음과 같이 수정하면 된다.
FE