반응형 priority_queue1 [백준/C++] 보석 도둑 (No. 1202) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정렬을 이용해 가장 가치가 높은 보석부터 가방에 넣을 수 있는지 확인하고, 무게가 가장 비슷한 가방에 넣으면 되겠다는 생각을 했다. 하지만, 문제는 사용한 가방에 있었다.이분 탐색으로 적절한 가방을 찾는 과정에서 이미 사용한 가방을 삭제하지 않고 처리할 적당한 방법이 떠오르지 않았다.(만약 삭제할 경우 삭제하는 과정에서 O(N)의 시간복잡도가 필요하기 때문에 문제의 시간복잡도는 O(N^2)이 된다.) 그래서 반대로 가방의 무게를 기준으로 보석을 찾도록 방법을 바꿨다. 하나의 가방에는 하나의 보.. 2024. 6. 12. 이전 1 다음 반응형