취미로 코딩하기

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

이번에 볼 문제는 백준 1092번 문제인 배이다.
문제는 아래 링크를 확인하자.

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

무거운 화물을 옮길 수 있는 크레인이 정해져있다는 점에서 착안해, 매 초마다 "가장 무거운 짐을 옮길 수 있는 크레인"부터 순서대로 "그 크레인이 들 수 있는 짐"을 하나 옮기는 것을 반복해나가는 것으로 문제를 해결할 수 있다.

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

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

int N, M;
int lmt[50];
priority_queue<pair<int, int>> pq[50];
bool visited[10000];

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> lmt[i];
	sort(lmt, lmt + N);
	cin >> M;
	for (int m = 0; m < M; m++) {
		int x; cin >> x;
		if (x > lmt[N - 1]) {
			cout << -1;
			return 0;
		}
		for (int i = 0; i < N; i++) {
			if (x <= lmt[i]) pq[i].push(make_pair(x, m));
		}
	}

	int ans = 0;
	while (M) {
		ans++;
		for (int i = N - 1; i > -1; i--) {
			while ((!pq[i].empty()) && visited[pq[i].top().second]) pq[i].pop();
			if (!pq[i].empty()) visited[pq[i].top().second] = 1, M--;
		}
	}

	cout << ans;
}