글 읽기 - 우선순위 큐를 사용하면 안되는건가요?

dudgh9661 3년 전 0

우선순위 큐의 정렬 기준은,

1. 마감일이 빠른 순

2. 마감일이 같으면, 점수가 높은 순

vec 안에 모든 과제 정보를 담고, vec[0] ~ vec.size()까지 각 vec[n]이 첫번째 과제로 수행되었을 때의 값들을 계산해주었습니다. 그리고 그 값들 중 최댓값이 답이라고 생각하여 출력했으나 틀렸다고 나옵니다...

제 로직에 어떠한 부분이 모순인건가요?

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

using namespace std;

int N;

typedef struct work{
    int day;
    int score;
}WORK;

struct cmp{
    bool operator()(WORK a, WORK b) {
        if( a.day == b.day ) {
            return a.score < b.score;
        }
        return a.day > b.day;
    }
};
priority_queue< WORK, vector<WORK>, cmp >  pq;
vector< WORK > vec;

void init() {
    cin >> N;
    int a, b;
    for(int i = 0; i < N; i++) {
        cin >> a >> b;
        vec.push_back({a,b});
    }
}

void Enque(int idx) {
    for(int i = 0; i < vec.size(); i++) {
        if( i == idx ) {
            continue;
        }

        pq.push({vec[i].day, vec[i].score});
    }
}
int sol(int idx) {
    int sDay = vec[idx].day; //1일차에 처리할 일을 정함
    int sVal = vec[idx].score;
    Enque(idx);

    int Day = 2; //위에서 미리 정했던 일을 처리했으므로 2일부터 시작.
    int sum = sVal;
    while( !pq.empty() ) {
        int remDay = pq.top().day;
        int remVal = pq.top().score;
        pq.pop();

        if( remDay >= Day ) {
//            cout << "cur : " << curDay << " score " << curVal << endl;
            sum += remVal;
            Day++;
        }
    }
    cout << idx << "일 때 : " << sum << endl;
    return sum;
}
int main() {
    init();
    int MIN = -1;
    for(int i = 0; i < vec.size(); i++) {
        int res = sol(i);
        if( MIN < res ) MIN = res;
    }
    cout << MIN << endl;
    return 0;
}

nahwasa 3년 전 2

반례입니다.

dudgh9661 3년 전 1

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

우선순위 큐를 사용하면 안되는건가요?

dudgh9661 3년 전 0

nahwasa 3년 전 2

dudgh9661 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말