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

• 문제 링크 : boj.kr/29155
• 난이도 : S3
• 태그 : 정렬, 그리디

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

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    int goal[5] = {};
    for(int i = 0; i < 5; i++) {
        cin >> goal[i];
    }
    vector<int> p[5];
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        p[a-1].emplace_back(b);
    }
    int ans = 240;
    for(int i = 0; i < 5; i++) {
        sort(all(p[i]));
        for(int j = 1; j < goal[i]; j++) {
            ans += p[i][j];
        }
        ans += p[i][goal[i]-1];
    }
    cout << ans;

    return 0;
}

---

풀이

모든 난이도의 문제를 풀어야 하므로 기본적으로 240분이 걸린다.

한 난이도 내에서 문제를 푸는 데에 걸리는 시간을 구해보자.

같은 난이도에서 문제를 풀 때는 이전의 문제와 푸는 시간의 차이만큼 쉬어야 한다.

어떤 두 문제를 푼다고 했을 때, 두 문제를 푸는 총 시간은 결국 둘 중 오래 걸리는 시간 * 2 만큼 걸린다.

이를 최소화하기 위해 시간이 적게 걸리는 문제부터 풀어가며 계산하면 해결할 수 있다.