개요

[링크]백준 13904번: 과제

입력
첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력
얻을 수 있는 점수의 최댓값을 출력한다.

접근 방식

• 점수대로 정렬을 한 뒤,
  해당 날짜에 해당하는 벡터. second에 점수를 넣어준다.
  만약, 해당 벡터에 점수가 이미 등록되어 있다면
  등록되어있는 점수와 비교한다.
  이미 등록된 점수보다 크면 교체하고
  작다면 이전 날짜에 저장된 값과 또 비교 후
  크면 교체하기를 반복한다.
  

코드

#include<iostream>									//3
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int arr[1001];											//점수대로 정렬후 며칠차에 어떤 과제를 하는게 좋은지 저장하는 배열
vector<pair<int,int>> v;
bool comp(pair<int, int> a, pair<int, int> b) {			//점수대로 정렬하는 비교함수
	return a.second > b.second;
}

void input(int& maxDate) {										//입력함수 
	int amountH=0,tempD=0,tempW=0;
	cin >> amountH;
	for (int i = 0; i < amountH; i++) {
		cin >> tempD >> tempW;
		maxDate = tempD > maxDate ? tempD : maxDate;
		v.push_back(make_pair(tempD,tempW));
	}
}

void solution(const int& maxDate) {
	int ans = 0,idx=0;
	sort(v.begin(), v.end(),comp);										// 점수대로 정렬
	for (int i = 0; i < v.size();i++ ) {
		int day = v[i].first;											//v[i].first값을 day에 저장
		while (day>1 && arr[day] != 0 && arr[day]>=v[i].second) day--;	//만약 해당 날짜에 이미 다른 값이 저장되어있다면 그 앞날짜로 index를 옮겨준다.
		if(arr[day]<v[i].second) arr[day]= v[i].second;					//만약 arr[day]이 비어있다면 넣어준다.

																		
	    
	}
	for(int i=1;i<=maxDate;i++)
		ans += arr[i];
	cout << ans;

}

int main() {
	int maxDate=0;
	input(maxDate);
	solution(maxDate);
}

문풀후생

처음에 이 방식을 이용해 풀 때
벡터에 등록되어있는 값과 비교 후
작으면 앞값과 비교하는 과정을 거치지 않고
계속 앞에 넣어줬다가 틀렸다.