취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17225번 문제인 세훈이의 선물가게이다.
문제는 아래 링크를 확인하자.

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

선물 주문은 많아야 10만개 들어올 수 있고 각 선물은 많아야 300의 시간을 소비해 포장하게 되므로, 길어야 3000만 + (포장시작 시간 상수)정도의 시간 안에 모든 선물의 포장이 완료됨을 알 수 있다.

따라서 시각 1부터 3000만+(상수)까지의 각 시각을 따라 선물 포장 과정을 시뮬레이션하는 것으로 문제를 해결할 수 있다.

반복문으로 구현할 경우, 같은 시각에 여러 선물을 포장할 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int A, B, N;
vector<pair<int, int>> vecA, vecB;
int waitingA, waitingB, cntA, cntB;
vector<int> ansA, ansB;
int gid;

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

	cin >> A >> B >> N;
	while (N--) {
		int t, x; char c; cin >> t >> c >> x;
		if (c == 'B') vecA.emplace_back(make_pair(t, x));
		else vecB.emplace_back(make_pair(t, x));
	}
	sort(vecA.begin(), vecA.end(), greater<>());
	sort(vecB.begin(), vecB.end(), greater<>());

	for (int t = 1; t < 33333333; 1) {
		if (!vecA.empty() && vecA.back().first <= t && waitingA <= t) {
			waitingA = t + A;
			vecA.back().second--;
			if (!vecA.back().second) vecA.pop_back();
			ansA.emplace_back(++gid);
		}
		else if (!vecB.empty() && vecB.back().first <= t && waitingB <= t) {
			waitingB = t + B;
			vecB.back().second--;
			if (!vecB.back().second) vecB.pop_back();
			ansB.emplace_back(++gid);
		}
		else t++;
	}

	cout << ansA.size() << '\n';
	for (auto &x:ansA) cout << x << ' ';
	cout << '\n';
	cout << ansB.size() << '\n';
	for (auto &x:ansB) cout << x << ' ';
}