처음 제출했던 코드가 7퍼센트까지 채점되고 틀렸다고 떠서, 로직을 다시 확인했다.
근데 아무리 봐도 로직상 틀린 부분이 파악이 안 되어서 혹시나 하고 숫자 범위를 확인했는데, 보석 하나의 최대 가격이 1,000,000원이고 최대 갯수는 30,000개이기 때문에 둘을 곱하면 int 자료형의 숫자 범위를 벗어나게 된다. (int 자료형은 최대 약 20억까지 저장할 수 있다.)
따라서 result 변수의 자료형을 long long으로 수정했더니 정답을 맞출 수 있었다.
처음에는 보석의 값이 가장 높은 것은 무조건 포함해야 한다고 생각하고, 보석의 값이 높은 순으로 정렬을 한 상태에서 가방에 순서대로 넣는 것을 떠올렸다. 그런데 이렇게 하게 되면 보석의 무게에 따라서 가방에 적절히 분배하기가 어려웠다.
보석의 값과 무게 사이에 어떠한 관계식이 전혀 없기 때문에, 하나의 보석을 살펴볼 때마다 어느 가방에 넣는 것이 적절한지 일일이 살펴봐야했다. 하지만 이 방법은 n^2의 시간 복잡도를 가지면서 시간초과가 날 듯 하여, 다른 방법을 생각하게 되었다.
두 번째로 생각한 방법은, 가방을 가벼운 것부터 먼저 나열을 하고, 가방을 순서대로 순회하면서 각 가방에 넣을 수 있는 최대치의 보석을 담는 방법을 떠올렸다.
→ 가벼운 것부터 살펴본 이유는, 가방의 최대 무게보다 보석의 무게가 더 무거울 경우, 아무리 비싼 보석이라도 그 보석은 가방에 담지 못하기 때문이다. 따라서 가벼운 보석들을 가벼운 가방에 먼저 넣되, 각 가방에 넣을 수 있는 최대 값어치를 넣는 것이 합리적이라고 생각했다.
따라서 각 가방의 최대 무게 한도를 만족하면서, 각 가방에 넣을 수 있는 최대 값어치의 보석을 넣는 방법을 떠올렸다.
단, 시간 복잡도를 생각했을 때, for문을 중첩하지 않고 단일 for문으로만 해결할 수 있어야 한다.
→ 오름차순으로 정렬한 가방을 순서대로 순회하면서, 해당 가방보다 무게가 가볍거나 똑같은 보석들을 리스트에 추가하고, 그 중에서 가장 비싼 보석을 가방에 넣는 것이다.
→ 따라서 보석들도 무게를 기준으로 오름차순으로 정렬을 하였다.
→ 그리고 현재 가방에 넣을 수 있는 보석 리스트에 보석이 추가될 때마다 가격을 기준으로 곧바로 내림차순 정렬이 이뤄져야 하므로, 최대 힙을 사용하였다.
→ 따라서 최대 힙은, 현재 보고 있는 가방에 넣을 수 있는 보석들의 리스트 역할을 하며, 그 중 가장 무거운 보석을 뽑을 수 있다.
따라서 코드 흐름은 아래와 같이 설정했다.