백준 13904 c++ "과제" -PlusUltraCode-

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

 

 

[필자 사고]

보통 과제일이 촉박하면 작은 값을 우선순위로 해서 정렬을 한다.

다만 이 문제는 함정이 있다. 해당 형태로 정렬을 하게 되면 이 문제를 풀지 못하게 된다.

과제 가치와 과제일이 많은것을 우선순위로 정렬을 한 뒤 과제일을 기준으로 vistied배열을 선언한여 

적당한 날짜에 갱신하는 형태로 해당 문제를 해결해야 된다. 

당연히 작은 숫자가 먼저 우선순위 와야 문제를 해결할 수 있다는 사고에서 벗어나게 해준 문제라고 생각한다.

아래는 자세한 코드 해설이다.

[코드 해설]

 

• Input 함수
  • 사용자로부터 과제 수 N을 입력받고,
    N개의 (마감일, 점수) 데이터를 우선순위 큐에 넣습니다.
  • 우선순위 큐는 점수가 높은 순으로 과제를 정렬합니다.
• Game_Start 함수
  • visited 배열을 초기화해 날짜별 수행 여부를 기록합니다.
  • 큐에서 점수가 가장 높은 과제를 하나씩 꺼내며 다음을 수행합니다:
    • 해당 과제의 마감일부터 거꾸로 날짜를 확인하며,
    • 아직 과제를 수행하지 않은 날이 있으면,
      • 해당 날짜에 과제를 배정하고 점수를 누적합니다.
      • 그 날짜는 visited로 표시하여 더 이상 사용하지 않습니다.
  • 이 과정을 반복하여 가능한 모든 과제를 배정합니다.
• 결과 출력
  • 최종적으로 누적된 점수(resultSum)를 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> Node;

struct cmp {
	bool operator()(Node a, Node b) {

		if (a.second == b.second) {
			return a.first < b.first;
		}
		return a.second < b.second;
	}
};

int N;
priority_queue<Node, vector<Node>, cmp > pq;
vector<bool> visited;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int day, num;
		cin >> day >> num;
		pq.push({ day,num });
	}
}

void Game_Start() {
	visited.assign(1001, false);
	int resultSum = 0;

	while (!pq.empty()) {
		int endDay = pq.top().first;
		int score = pq.top().second;

		for (int i = endDay; i >= 1; i--) {
			
			if (visited[i] == true) {
				continue;
			}
			else if (visited[i] == false) {
				resultSum += score;
				visited[i] = true;
				break;
			}
		}

		pq.pop();
	}

	cout << resultSum;
}

int main(void) {
	Input();
	Game_Start();
}