⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.
이제 슬슬 재활운동도 끝나가고 골드 문제를 풀기 시작했습니다. 골드 문제정도만 풀어도 대부분의 코테를 통과할 수 있다고 하는데요. 근데 골드 문제가 한두개도 아니고 수천개가 되니까... 문제에 압도되지 말고 그래도 풀어야 겠죠?
해당 문제는 과제 남은 날짜와 과제를 처리하면 얻는 점수가 있는 문제입니다. 이제 이런 문제를 보면 최대 점수를 얻을 수 있는 문제를 선택하는 문제라는 것은 감으로 알 수 있습니다. 그래서 이 문제 또한 그러한 문제입니다.
해당 문제를 보면, 과제의 개수 N이 주어지고 그에 따른 입력이 쌍으로 들어옵니다. {날짜, 점수} 이런식으로 주어지고 있기 때문에, 해당 문제를 어떤 순서로 해결해야 최고 점수를 얻을 수 있을까를 고민해야 합니다.
문제를 보면, 그러한 생각이 듭니다. 만약 {1,10}, {1,10}, {1,10}, {100,1000} 이라면? 굳이 하루 남은 과제이지만 10점 짜리를 풀어야 할까요? 아닙니다. 100일이 남았지만 1000점 짜리 과제를 푼다면? 100일 짜리를 미리 풀어 점수를 1000점을 획득하고 당장 하루짜리는 혼나면 그만입니다.
그렇다면, 우리가 이 문제를 풀기위해선 정렬을 먼저 해야한다는 부분이 생각납니다.
정렬의 순서는 점수가 큰것 그리고 날짜가 많이 남은 것을 먼저 푼다면? 최고 점수를 얻을 수 있을 것입니다.
그렇지만? 해당 날짜에 해당하는 문제를 먼저 푸는 것이 좋겠죠? 심지어 해당 날짜에 가장 높은 점수를 푸는 것이 좋을 것입니다. 그렇다면? 해당 날짜에 해당하지만 두번째 순위지만? 해당 날짜에 접근하진 못하지만? 해당 날짜보다 전인 날짜에서는 내가 짱이야? 내 점수가 짱이다 그러면 그 날짜에 들어가게 되는 겁니다. 그렇게 된다면? 자연스럽게 해당 날짜에 최고 점수는 그 날짜에 들어가면서(이미 정렬을 해주었기 때문에 가능합니다!) 해당 날짜는 아니지만 점수가 너무 높아서 이전 날짜에 포함을 시켜 최고의 점수를 받을 수 있게 되는 것입니다.
저는 일단 우선순위 큐로 {날짜, 점수}를 정렬을 자동으로 해줬고, 우선순위 큐에서 값을 빼내면서 날짜에 해당하는 visited배열에 원래 변수 이름을 day로 설정해야하는데 날짜 선정할때 써서 그렇게 하지 않았습니다. 하여튼 해당 배열에 체크를 해줘가면서 최고 점수를 얻는 방식을 사용했습니다. 아래는 정답 코드입니다.
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct INFO{
int day;
int score;
};
struct cmp{
bool operator()(const INFO& a, const INFO& b){
if(a.score == b.score){
return a.day < b.day;
}
return a.score < b.score;
}
};
priority_queue<INFO, vector<INFO>, cmp> pq;
int n,day,score;
int main() {
cin >> n;
for(int i = 0; i < n; i++){
cin >> day >> score;
pq.push({day,score});
}
int answer = 0;
int visited[1001];
memset(visited,0,sizeof(visited));
while(!pq.empty()){
INFO temp = pq.top();
pq.pop();
day = temp.day;
score = temp.score;
for(int i = day; i >= 1; i--){
if(visited[i]) continue;
else{
answer += score;
visited[i] = 1;
break;
}
}
}
cout << answer;
return 0;
}