2 2
4 1
0 1
1
4
정답 : 2
출력 : 1
2 2
9 9
9 1
9
6
정답 : 9
출력 : 0
이 코드는 시간초과가 날듯 합니다...
1202번 - 보석 도둑
1. c++에서 long은 int랑 범위가 같아서 오버플로우 확률이 높습니다. 그러니 long long으로 변환해주시고
2. 가방의 무게는 보석과 같아도 됩니다. < 연산자를 <= 연사자로 변경해야할 것 같습니다.
3. 마지막으로, 처음에 만난 가방에 들어갈 보석이 최대라는 보장이 없습니다. 따라서, 우선순위 큐에 해당 가방에 들어가는 모든 보석을 넣고 다음 가방으로 넘어가기 전에 우선순위 큐 안에서 최대 값을 하나 뽑아서 다음 가방으로 이동하시는 것이 최댓값입니다. 다음 가방으로 넘어가면서 큐를 전부 비우지 않는 이유는 다음 가방에 들어가기 적절한 보석들은 이전 가방에서도 적절한 보석입니다 (가방을 무게 순서대로 정렬했으므로). 또한, 무게가 늘수록 값이 늘어난다는 보장이 없기 때문에 이전 가방에서 후보로 넣은 보석들도 들고가야합니다.
댓글을 작성하려면 로그인해야 합니다.
jwsept 1년 전
시간초과는 안 뜨는데 틀렸다고 뜨네요