백준 29155 (C++) 개발자 지망생 구름이의 취업 뽀개기

최초 업로드: 2025-09-28 18:56:16

최근 수정 시간: 2025-09-28 18:56:16

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] 개발자 지망생 구름이의 취업 뽀개기

[문제 링크](https://www.acmicpc.net/problem/29155)

## 문제 설명

구름 LEVEL은 코딩 테스트를 처음 준비하는 취업 준비생들을 위한 다양한 서비스와 콘텐츠를 제공하는 구름의 서비스이다. 취업 준비를 하는 개발자 지망생 구름이는 구름 LEVEL에서 제공하는 알고리즘 문제들을 풀어보려고 계획 중이다.

구름이의 계획은 다음과 같다. 구름 레벨에는 난이도 $1$부터 난이도 $5$까지 문제들을 제공하며, 구름이는 난이도 $1$부터 난이도 $5$까지 난이도가 같거나 증가하는 순서대로 문제를 풀 것이다. 구름이는 문제들의 지문을 보고 살펴본 $N$개의 문제들을 푸는 데 걸릴 예상 시간을 모두 체크해 보았다. 각 문제와 문제 사이에는 휴식 시간이 필요한데 이는 만약 두 문제가 같은 난이도라면 두 문제를 푸는 데 걸리는 시간의 차이만큼 필요하고 난이도를 증가시키는 경우 $60$분의 시간이 필요하다. 즉, 구름이가 문제를 푸는 데 걸리는 시간은 푼 문제의 예상 시간 합과 문제 사이 휴식 시간의 합만큼 걸린다.

구름이는 각 난이도별로 풀어볼 문제 수를 정하였다. 계획한 문제를 푸는 데 필요한 최소 시간을 구하여 구름이가 취업에 성공할 수 있도록 도와주자.

## 입력

첫째 줄에 구름이가 살펴본 문제 수 $N$이 주어진다. $(5 \leq N \leq 1\,000)$

둘째 줄에 각 난이도별로 풀어야 하는 문제 수 $p_1, p_2, p_3, p_4, p_5$가 공백으로 구분되어 주어진다. $(1 \leq p_i \lt N;$ $1 \leq i \leq 5)$

셋째 줄부터 $N$개의 줄에 걸쳐 문제의 난이도 $k_i$와 푸는 데 걸리는 시간 $t_i$가 공백으로 구분되어 주어진다. $(1 \leq k_i \leq 5;$ $1 \leq t_i \leq 300)$

$1\leq j \leq 5$인 $j$에 대하여 난이도 $j$인 문제의 개수는 $p_j$ 이상이다.

## 출력

계획한 문제를 푸는 데 필요한 최소 시간을 출력하시오.

## 풀이
각 난이도마다 정렬하여 작은 것부터 $p_i$개씩 선택했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int p[5];
vector<vector<int>> problem(5);

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<5;i++) cin >> p[i];

while(n--) {
        int k, t; cin >> k >> t;
        problem[k-1].push_back(t);
    }

int total=240;
 for(int i=0;i<5;i++) {
 sort(problem[i].begin(), problem[i].end());
 for(int j=1;j<p[i];j++) {
 if(j) total += problem[i][j]-problem[i][j-1];
 total += problem[i][j];
 }
 }
 cout << total;
}
```