문제 URL : programmers.co.kr/learn/courses/30/lessons/12927
코딩테스트 연습 - 야근 지수
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도
programmers.co.kr
문제접근법 :
남은작업량들의 제곱의 합들이 피로도인데 피로도의 수치를 가장 적게 만드는 법을 구하는 문제이다.
n번 1개씩만 줄여나가야하기 때문에 제곱을 작게만드는건 결국 가장 큰값을 하나씩 줄여야
작게 만드는데 이것을 계속 큰값만 줄여나가기 위한 자료구조를 선택하기위해선 우선순위 큐를 사용하면 바로 해결가능하다
조건1: 가장큰값을 줄여나가면서 0이되는수는 아예 작업량에서 지워버려야한다
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
long long solution(int n, vector<int> works) {
long long answer = 0;
priority_queue<long long> pq;
for (int i = 0; i < works.size(); i++)
pq.push(works[i]);
while (n--&&!pq.empty())
{
int t = pq.top();
pq.pop();
if (t - 1>0){
pq.push(t - 1);
}
}
while (!pq.empty())
{
long long t = pq.top();
pq.pop();
answer += t*t;
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 혹은 제 논리가 맞지않는것이 있다면 언제든 댓글을 이용해주시길 바랍니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 2018 KAKAO BLIND RECRUITMENT[3차] n진수 게임 (0) | 2021.03.19 |
|---|---|
| 프로그래머스 합승 택시 요금 (2021 KAKAO BLIND RECRUITMENT ) (0) | 2021.02.17 |
| 프로그래머스 섬 연결하기 (0) | 2020.09.09 |
| 프로그래머스 [3차] 자동완성(2018 KAKAO BLIND RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 [1차] 뉴스클러스터링(2018 KAKAO BLINED RECRUITMENT) (0) | 2020.09.09 |
