취미로 코딩하기

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

이번에 볼 문제는 백준 23254번 문제인 나는 기말고사형 인간이야이다.
문제는 아래 링크를 확인하자.

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

매 시간마다 추가로 올릴 수 있는 점수가 높은 과목을 선택해 공부하자.

우선순위 큐(priority queue)를 이용하면 매 시간마다 가장 높은 순서를 빠르게 접근할 수 있다.

해당 과목을 1시간 공부하고 나면 100점까지 남은 점수가 원래 1시간 공부해서 오를 점수보다 적어질 수 있음에 유의하자.

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

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

int A[200000];
int B[200000];
priority_queue<pair<int, int>> pq;

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

	int N, M; cin >> N >> M;
	N *= 24;

	for (int i = 0; i < M; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];

	for (int i = 0; i < M; i++) {
		if (A[i] < 100) pq.push(make_pair(min(B[i], 100 - A[i]), i));
	}

	while ((N--) && !pq.empty()) {
		int a = pq.top().second, b = pq.top().first;
		A[a] += b;
		pq.pop();
		if (A[a] < 100) pq.push(make_pair(min(B[a], 100 - A[a]), a));
	}

	int ans = 0;
	for (int i = 0; i < M; i++) ans += A[i];

	cout << ans;
}