[S2] 백준 24938번 키트 분배하기 C++ 그리디 알고리즘, 덱

리뷰

 

https://www.acmicpc.net/problem/24938

Solve.ac에 있는 주간문제를 알고리즘 분류를 안보고 풀어보았다. 그런데 그리디 알고리즘 문제가 나왔군

 

전역 변수

• n : 방의 개수를 저장할 변수
• total : 키트의 총 개수를 저장할 변수
• ans : 발생하는 혼잡도의 총 값을 저장하고 출력할 변수
• kit : 각 방마다 보유한 키트의 개수를 입력 받을 정수형 배열, 크기는 20만으로 초기화 한다.
• Node : 키트를 더 많이 갖고 있는 방에서 남는 키트 정보를 저장할 구조체
• deq : 방의 순서대로 남은 키트를 수거하여 갖고 있는 키트를 관리할 Node타입 덱

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 n번의 for문을 순회해 준다.
2. kit의 i번째 인덱스에 해당 방이 보유한 키트 수를 입력받아 준다.
3. total변수에 각 방이 보유한 키트의 수를 더해 총 키트 수를 초기화해 준다.
4. div변수에 total / n한 값을 받는다, 이는 각 방에 존재해야할 키트의 개수이다.
5. 다시 n번의 for문을 순회하고 div개 초과 키트를 보유한 방에서 남는 키트와 방번호를 deq에 추가해 준다.
6. 다시 n번의 for문을 순회하고 div개 미만 키트를 보유한 방이 만나면 deq에서 꺼내 키트를 분배해 준다.
7. deq이 비지 않았고, i번째 방의 키트가 아직 div보다 작다면 계속해서 수행해 준다.
8. deq의 맨 앞 요소를 꺼내주고, 모자란 만큼 키트를 방에 전달한다.
9. 만약 키트를 충분히 전달했는데 아직 개수가 남았다면 deq의 앞쪽에 남은 키트와 방번호를 추가해 준다.
10. 모든 반복 작업을 마친 후 ans에 저장된 값을 출력해 준다.

 

참고 사항

우선순위 큐를 사용해도 될 것 같다, pq를 쓴다면 인덱스 오름차순으로 정렬하면 될듯?

 

 

정답 코드

#include<iostream>
#include<deque>
#define ll long long

using namespace std;

ll n, total, ans;
ll kit[200000];

struct Node{
	ll cnt, idx;
};

deque<Node> deq;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> kit[i];
		total += kit[i];
	}

	ll div = total / n;
	for (int i = 0; i < n; i++) {
		if (kit[i] > div) deq.push_back({ kit[i] - div, i });
	}

	for (int i = 0; i < n; i++) {
		if (kit[i] < div) {
			while (!deq.empty() && kit[i] < div) {
				Node node = deq.front(); deq.pop_front();
				ll cnt = node.cnt, idx = node.idx;
				ll need = min(div - kit[i], cnt);
				kit[i] += need;
				kit[idx] -= need;
				ans += need * (abs(i - idx));
				cnt -= need;
				if (cnt) deq.push_front({ cnt, idx });
			}
		}
	}
	cout << ans;
}