[백준 16237] 이삿짐센터

 전에도 말했다시피 그리디에는 우선순위 큐가 굉장히 많이 쓰인다.
우선순위큐의 특징이 그리디라는 문제유형의 상황에 적합하기 때문이다.
이 문제도 아래와 같이 구현유형을 푼다는 생각으로 풀 수 도 있지만 우선순위큐를 사용하는 방식으로 풀어봄
 

arr = list(map(int,input().split()))
cnt = 0

# 다 담을때까지
while sum(arr)!=0 :
    bag = 5

    for i in range(4,-1,-1) :
        # 물건이 존재하고 계속담기가능할때까지
        while arr[i]>0 and bag-(i+1)>=0 :
            arr[i]-=1
            bag-=(i+1)
    cnt+=1
    
print(cnt)

 

---

[우선순위큐를 사용한 그리디 구현 방식]

 
1. 우선 5kg은 그리디 계산을 해줄 필요가 없다
왜냐하면 5kg은 더 이상 채울 수 없기 때문이다.
그래서 5kg은 나중에 cnt + arr[5] 해준다.
 
2. 4kg 과 3kg 은 부분적 예외이다
그리디 계산에서 완벽하게 제외되는 놈들은 아니지만 무게를 내림차순 순서로 pq에 저장한다는 과정을 생각해보면 
1kg 과 2kg 은 아직 pq에 들어오지 않았으므로 추후에 1kg 2kg 가 들어오면 그리디 계산에 필요하지만
이들이 없을때는 그리디 계산을 할 필요가 없다!
따라서 그냥 개수만큼 pq에 저장해준다.
 
3. 1kg 2kg이 그리디 계산을 거쳐야하는 놈들이다
얘내는 한 묶음으로 들어갈 수 있는 종류가 굉장히 다양하다
4+1 / 3+2 / 3+1+1 / 2+2+1 / 2+1+1+1 / 1+1+1+1+1 이렇게 다양한 조합이 가능한데
이걸 상황별로 케이스를 다 나눠서 브루트포스로 처리할 수는 없는 일이다. 따라서 그리디로 처리해주면 된다.
 
4. pq.size()==0 은 3 4 5 가 모두 0일때의 예외처리이다
while문 안에 들여넣기에는 굉장히 보기 불편한? 코드지만
구지 저 상황일때를 대비해서 넣어두는게 보기 싫은 코드지만 여기서까지 클린코드를 신경쓰진 않겠다
 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int arr[6];
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 1; i <= 5; i++) {
		cin >> arr[i];
	}

	// pq에 4는 그냥 넣어줘도 무방하다
	for (int i = 0; i < arr[4]; i++) pq.push(4);
	for (int i = 0; i < arr[3]; i++) pq.push(3);

	for (int i = 2; i >= 1; i--) {
		// 해당 kg 다 빌때까지
		while (arr[i]) {
			if (pq.size() == 0) {
				pq.push(i);
			}
			else {
				int minweight_bag = pq.top();

				if (minweight_bag + i > 5) {
					pq.push(i);
				}
				else {
					pq.pop();
					pq.push(minweight_bag + i);
				}
			}
			arr[i]--;
		}
	}

	// 5kg은 그냥 더해주면 된다
	cout << pq.size() + arr[5];
	return 0;
}