[백준 / BOJ] C++ 29155 개발자 지망생 구름이의 취업 뽀개기

29155번: 개발자 지망생 구름이의 취업 뽀개기

 

문제

https://www.acmicpc.net/problem/29155

29155번: 개발자 지망생 구름이의 취업 뽀개기

 

 

풀이

각 난이도 별로 문제를 푸는 데 걸리는 시간을 저장하고 오름차순으로 정렬한다. 각 난이도별로 풀어야하는 문제의 수만큼 앞에서부터 고르면 된다.

이 문제에서는 문제를 푸는 데 필요한 시간을 최소화하고 휴식시간도 최소화해야한다. 휴식시간은 같은 난이도 문제 사이에는 걸리는 시간의 차 만큼 휴식시간이 필요하다. 문제가 푸는 데 오래 걸리는 문제일수록 휴식시간도 늘어나는 것은 직관적으로 알 수 있으므로 푸는데 걸리는 시간이 적은 문제들만 고르면 된다.

그리고 각 난이도 사이엔 이와 관계 없이 60분의 휴식이 필요하다. (조건문으로 문제를 풀었지만, 각 난이도에서 1문제 이상 풀어야함이 조건으로 주어져있기 때문에 240분을 더한 다음 시작해도 된다.)

 

 

코드

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  // 풀어야하는 문제 수
  int p[6];
  for (int i = 1; i <= 5; i++)
    cin >> p[i];
  // x번 문제를 푸는 데 y분 걸린다.
  vector<vector<int>> t(6);
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    t[x].push_back(y);
  }
  // 난이도별 오름차순 정렬
  for (int i = 1; i <= 5; i++)
    sort(t[i].begin(), t[i].end());
  int ans = 0;
  int cnt = 0;
  for (int i = 1; i <= 5; i++) {
    cnt++;
    for (int j = 0; j < p[i]; j++) {
      if (j == 0) { // 현재 난이도의 첫번째 문제인 경우
        ans += t[i][j]; // 문제를 푸는 데 걸리는 시간 추가
        if (cnt != 1) { // 난이도가 1이 아닌 경우
          ans += 60; // 휴식시간 60분 추가
        }
      } else { // 현재 난이도의 첫번째 문제가 아닌 경우
        ans += 2 * t[i][j] - t[i][j - 1]; // 다음 문제를 푸는 데 걸리는 시간 + 휴식시간 추가
      }
    }
  }
  cout << ans;
  return 0;
}