백준 [13904] 과제

출처 : https://www.acmicpc.net/problem/13904

13904번: 과제

 

 

	#include<iostream>
	#include<queue>
	using namespace std;
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, d, w; // d - 과제마감일, w - 과제점수
	priority_queue<pair<int, int>> pq;
	bool visited[1001] = {};
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
	cin >> d >> w;
	pq.push({ w, d });
	}
	while (!pq.empty()) {
	int score = pq.top().first;
	int deadline = pq.top().second;
	pq.pop();
	for (int i = deadline; i >= 1; i--) {
	if (!visited[i]) {
	visited[i] = true;
	ans += score;
	break;
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw 13904.cpp hosted with ❤ by GitHub

우선순위 큐를 사용해서 푸는 문제

점수가 높은 순으로 정렬해준다음, 과제를 하루에 하나씩 할 수 있다고 했으므로 각 과제를 할 날을 지정한다.

해당 일자에 다른 과제를 이미 하기로 했으면(방문한 적이 있다면), 날짜를 줄여가면서 찾기.

 

+ 배열을 선언할 때 전역으로 선언하면 초기화 해주지 않아도 되지만, 로컬로 선언할 경우 쓰레기값이 들어가서 초기화해줘야함.