야근지수

programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

bool cmp(long long a, long long b){
    return a>b;
}


long long solution(int n, vector<int> works) {
    
    long long answer = 0;
    vector<long long>v(n+1);
    long long total =0;
    priority_queue<int>pq; // 최대값을 항상 고려해야함: 우선순위 큐 쓰는 문제!!!
    for(int i=0; i<works.size(); i++){
       total += (works[i]*works[i]);
    }
    
    v[0]=total;
    int idx =0;
    
    for(int i=0; i<works.size(); i++){
        pq.push(works[i]);
    }
    
    //sort(works.begin(),works.end(),cmp);
    for(int i=1; i<=n; i++){
        int topnum = pq.top();
        topnum--;
        long long minus = topnum*2+1;
        if(v[i-1]<=minus){return 0;}
        else{v[i]= v[i-1]-minus;}
        pq.pop();
        pq.push(topnum);
       // --pq.top();
        
  
  }
    answer = v[n];
    return answer;
}

- priority queue 를 통해 매번 최대값을 1씩 빼주면 된다. 

- priority queue 대신 vector에 넣어서 sort 하면 시간 초과 뜸