[C++] 백준 23350번: K 물류창고

문제 링크

23350번: K 물류창고

문제 요약

물류창고에 물건이 컨베이어 벨트를 타고 들어온다. 물건은 우선순위와 무게를 가지고 있는데, 높은 우선순위의 물건이 위에 오도록 물건을 쌓아야 한다. 또, 우선순위가 동일한 물건들 사이에서는 무게가 무거운 물건이 아래에 오도록 쌓아야 한다. 물건을 한 번 들때마다 물건의 무게만큼 비용이 발생한다.
만약 현재와 다른 우선순위의 물건이 온다면 컨베이어의 시작 부분으로 해당 물건을 옮겨야 하고, 같은 우선순위의 물건들 사이에서 무거운 물건을 더 아래로 보내기 위해서는 나머지 공간에 물건들을 옮겼다가 다시 쌓아야 한다.
물건들을 모두 쌓는데 필요한 비용을 구해야 한다.

접근 방법

단순 구현 문제였습니다. 처음에는 컨베이어 벨트를 덱으로 구현했었는데, 제가 짠 코드에서는 덱을 큐로 완전히 대체할 수 있었기 때문에 큐로 다시 제출을 했습니다.

그렇게 효율적인 코드는 아닌데 입력이 작다보니까 전부 무난하게 통과를 하는 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<int> cnt(m + 1, 0);
	vector<vector<int>> containers(m + 1);
	queue<pair<int, int>> q;

	for (int i = 0; i < n; i++)
	{
		int p, w;
		cin >> p >> w;
		q.push({ p, w });
		cnt[p]++;
	}

	int lowest = m, ans = 0;
	while(!q.empty())
	{
		auto now = q.front();
		q.pop();

		if (now.first != lowest)
		{
			ans += now.second;
			q.push(now);
		}
		else
		{
			ans += now.second;
			cnt[lowest]--;

			if (!cnt[lowest])
				lowest--;

			if (containers[now.first].empty())
				containers[now.first].push_back(now.second);
			else
			{
				for (auto& i : containers[now.first])
				{
					if (i < now.second)
						ans += 2 * i;
					else
						break;
				}

				containers[now.first].push_back(now.second);
				sort(containers[now.first].begin(), containers[now.first].end());
			}
		}
	}

	cout << ans;
	return 0;
}