코딩하는 두꺼비

www.acmicpc.net/problem/11000

처음엔 강의시간의 길이로 접근해야 된다고 생각했는데 결국 강의 종료시간과 다음 강의 시작시간을 비교하는 것이 중요하다는 것을 알게 되었다.

1. 각 강의들을 벡터에 저장하고 정렬해준다.

2. 각 강의의 종료시간을 우선순위 큐에 저장해주고 다음 강의들의 시작시간과 우선순위 큐의 top을 비교해준다.

3. 만 우선순위 큐의 top이 시작시간보다 작다면 강의실을 늘리고 아니면 종료시간을 pop해준다.

이런식으로 알고리즘을 생각하고 풀었으며 생각보다 다른 문제들과 좀 다른 유형이라 고민을 꽤 오래했다.

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

priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int, int>> v;

int main() {
	int n,x,y, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		v.push_back({ x,y });
	}
	sort(v.begin(), v.end());
	pq.push(v[0].second);
	ans++;
	for (int i = 1; i < n; i++) {
		auto z = v[i];
		if (z.first >= pq.top()) {
			pq.pop();
		}
		else {
			ans++;
		}
		pq.push(z.second);
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/1715

우선순위 큐 분류에 들어가 있는 골드4 난이도의 문제였다.

이 문제 같은 경우엔 두 묶음을 골라 합치면 비교 횟수가 줄어 드는 것을 생각하고 풀면 쉽게 풀리는 문제였다.

최소 우선 순위 큐에 각 카드 묶음들을 넣어주고 계속 2개씩 꺼내어 더한 후 다시 넣어주는 식으로 구현하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, x, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		pq.push(x);
	}
	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		ans += a + b;
		pq.push(a + b);
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/2075

힙 혹은 우선순위 큐에 대해서 공부를 하기 위해서 문제를 찾던 도중 발견한 문제이다.

그냥 기본적인 우선순위 큐를 사용해서 푸는 문제인데 메모리 제한이 있어서 이부분을 생각해

pop()을 넣어주는 것이 중요한 문제였다.

또한 시간 초과를 겪었는데 이 부분은 cin, cout을 사용할 경우

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위와 같은 코드를 삽입해주어야 하고 아니면 그냥 scanf, printf를 사용해야 시간 초과가 나지 않는다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, x;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &x);
			pq.push(x);
			if (pq.size() > n) {
				pq.pop();
			}
		}
	}
	printf("%d", pq.top());
	return 0;
}

왜 난이도가 골드 4인지 약간 이해가 안되는 문제였다.. 아마 우선 순위 큐를 사용하지 않고 직접 구현하는 경우를 생각해서 그런 것 같다.