D[K]가 채워졌다고 바로 루프를 나가면 안 됩니다. 아래 예시를 봐주세요. 편의를 위해 순서대로 정렬을 해놨습니다. 작성하신 코드대로 갑니다.
우선 D[2]에 4가 들어갑니다.
이후, D[3]에 5, D[5]에 9가 들어갑니다.
다음으로 D[6]에 9가 들어갑니다.
그 후, D[K]인 D[6]이 채워졌으니 루프를 나가고 9를 출력합니다.
하지만 만약 여기서 안 나간다면 얘기가 달라집니다.
D[1]에 1이 들어오고 D[4]에 6이 들어가며, D[6]이 10으로 갱신됩니다.
즉, 최댓값을 얻으려면 루프를 중간에 나가지 않고 끝까지 돌아야 합니다.
bsm311 2년 전
무게당 가치순으로 정렬하고 중복되지 않으면 계속 D에 업데이트 해주는 식으로 구현했습니다.
계속 9%에서 틀렸습니다가 나오네요 ㅠㅠ
문제는 이런식으로 풀었습니다.
1. 우선순위 큐를 이용하여 무게당 가치(v/w)순으로 정렬
2. 큐가 empty하지 않을 경우 반복
1. D[K]가 0이 아니면 break
2. D[w]가 없으면 D[w] 초기화
3. set V에 있는 원소 origin_w, new_w = origin_w+w, D[new_w]가 비어 있으면 D[new_w] 초기화 및 new_w를 set에 넣어줌