JUNGLE_4주차

컴퓨팅 사고로의 전환 4주차

 

주차별 키워드

- 동적 프로그래밍, 그리디 알고리즘

 

더 고민해볼 키워드

- 비트필드를 이용한 다이나믹 프로그래밍 풀어보자

 

 

문제를 설명하는 능력이 아주 부족하다는 생각은 하고 있었지만, 이번 기회에 다시 한번 느낄 수 있었다. 

설명하는 연습도 꾸준히 해 나가도록 하자.

 

• 문제 정의
• 문제 해결 방안
• 구현 방법

---

 

SW사관학교 정글 WEEK04 시험

- 계단 오르기 click

- 내리막길 click [포스팅]

- 보석 도둑 click

 

 

 

보석 도둑💎

 

이번 주의 3번 문제였던 보석 도둑에 대해 알아보자.

도둑에게는 가방이 k개 있고, 각 가방에는 가방에 담을 수 있는 최대 무게보다 작거나 같은 보석을 1개씩 담을 수 있다. 이때, 훔칠 수 있는 보석 가격들의 합의 최대값을 구해야 한다.

 

단순히 정렬을 이용해 풀면 안되는 그리디 문제이다.

처음 접근할 때, 가방의 용량순으로 오름차순 정렬을 하고, 보석의 무게로 오름차순 정렬을 했다. 보석을 무게가 작은 것 부터 가방에 넣어보며, 담아지는 보석이면 바로 가방에 담았는데, 이렇게 풀리는 문제가 아니었다.

 

위의 방식에는 아래와 같은 반례가 존재한다.

100과 99의 가격을 가지는 보석을 담는 것이 가격의 합의 최대이지만, 위의 알고리즘으로 풀게 되면, 65와 99의 가격을 가지는 보석을 담게 된다.

3 2
1 65
5 100
2 99
2
5

 

 

 

solution

 

작은 용량을 가지는 가방부터, 해당 가방이 담을 수 있는 보석들 중 가격이 가장 비싼 보석부터 담아가야 한다!

 

우선 순위 큐 두개를 활용해 위의 방식을 구현할 수 있었다.

 

아래의 예제를 활용해 알아보자.

5 3
1 3
2 5
4 7
6 3
5 10
2
7
8

 

 

보석의 무게와 가격, 가방의 최대 무게들을 입력받는다. 

최대 무게 2,7,8을 가지는 가방들에 보석을 집어넣을 계획이다. 각 가방에 담을 수 있는 보석들을 왼쪽 박스(가방에 담을 수 있는 보석)에 추가해 놓고, 그중 가격이 최대인 보석을 가방에 집어넣자.

이때, 담을 수 있는 무게의 최대값이 작은 가방에 먼저 보석을 집어넣을 것이다.

 

(같은 무게, 같은 가격의 보석을 담아야 한다면 담을 수 있는 가방들 중 최대 무게가 최소인 가방에 집어넣는 것이 항상 유리하기 때문이다.)

 

 

 

• 우선 순위 큐에 보석들을 배열-[무게, 가격]형태로 집어넣는다. 이렇게 되면, 무게를 기준으로 최소힙이 만들어진다.

 

 

 

최대 무게가 2인 가방에 보석을 집어넣어 보자.

가방에 담을 수 있는 보석은 무게가 2보다 같거나 작은 보석들이다.

이들 중 가격이 가장 높은 보석을 (최대 무게 2인)가방에 넣자!

 

• 보석들을 저장해 놓은 우선순위 큐에서 무게가 2보다 큰 보석들만 남을 때 까지 pop한다. 
• pop한 보석들의 가격을 보석의 가격을 저장하는 또 다른 우선순위 큐에 최대힙으로 저장한다. 
• 무게가 2보다 작은 보석들의 가격이 저장된 우선순위 큐에서 최대 값을 pop해서 가방에 담는다.

 

 

 

 

다음으로 최대 무게가 7인 가방에 보석을 집어넣자!

아래의 그림과 같이 무게가 7 이하인 보석들은 모두 가방에 담을 수 있는 보석이다.

이 후보들 중 가장 가격이 높은 보석을 가방에 담는다.

 

 

• 보석들을 저장해 놓은 우선순위 큐에서 무게가 7보다 큰 보석들만 남을 때 까지 pop한다. 
• pop한 보석들의 가격을 보석의 가격을 저장하는 또 다른 우선순위 큐에 push한다. 
• 무게가 7보다 작은 보석들의 가격이 저장된 우선순위 큐에서 최대 값을 pop해서 가방에 담는다.

 

 

 

같은 방식으로 최대 무게가 8인 가방에 보석을 집어넣자.

 

 

 

 

최종적으로 아래와 같이 가격의 합이 최대인 보석들이 담긴다.

이렇게 우선순위 큐를 활용해 greedy문제를 풀 수 있다.👍👍

 

Code

import sys
from heapq import heappop, heapify, heappush
read=sys.stdin.readline

def main():
    n,k = map(int,read().split())
    jew = list(list(map(int,read().split())) for _ in range(n))
    heapify(jew)
    knapsacks = sorted(int(read()) for _ in range(k))

    cand = [] #현재 knapsack에 들어갈 수 있는 보석들의 후보
    total = 0 #보석 무게 총합
    for knapsack in knapsacks:
        while jew and jew[0][0] <= knapsack:
            heappush(cand,-heappop(jew)[1])
        if cand:
            total -= heappop(cand)

    print(total)
if __name__ == '__main__':
    main()

 

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]