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

문제링크 : https://www.acmicpc.net/problem/29155

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

 

작성코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N;                    // 문제 수
int arr[5];                // 풀 문제 수
vector<int> solNum[5];    // 난이도 별 풀 문제들
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < 5; ++i)
    {
        cin >> arr[i];
    }
 
    int k, t;
    for (int i = 0; i < N; ++i)
    {
        cin >> k >> t;
        solNum[k-1].push_back(t);
    }
 
 
    int result = 0;
    for (int i = 0; i < 5; ++i)
    {
        sort(solNum[i].begin(), solNum[i].end());
        for (int j = 0; j < arr[i]; ++j)
        {
            result += solNum[i][j];            // 풀이에 걸리는 시간
            if (j > 0)
            {
                result += abs(solNum[i][j] - solNum[i][j - 1]);        // 휴식 시간
            }
        }
        result += 60;
    }
 
    result -= 60;
 
    cout << result;
}
 

 

 

풀이

 

문제 풀이 시간을 최소한으로 하려면 가장 풀이시간이 적은 문제만 골라서 풀어야한다.

이를 위하여 풀이에 걸리는 시간을 정렬해주어 계산에 사용해주면 된다.

 

 

1. 난이도별 문제 갯수, 문제별 난이도, 풀이시간 입력받기

- 난이도별 문제 갯수는 arr 배열에 저장해준다.

- 모든 문제를 난이도별로 벡터 배열을 사용하여 저장해준다.

(입력된 문제의 수만큼만 난이도 별로 효율적으로 저장해두기 위하여)

 

2. 문제 풀이에 걸리는 최소 시간을 구하기 위해서는 가장 풀이 시간이 짧은 문제만 골라 풀어야한다.

- 입력된 문제들을 정렬하여 최소값이 앞에 오도록 한다.

- 풀어야하는 문제 수만큼 정렬된 문제의 풀이 시간을 더하고 휴식시간으로 이전 문제와의 풀이 시간 차이를 빼서 더해준다.

 

- 난이도 상승 시 휴식시간은 60분 이므로 난이도 내에서 도는 for문 (j) 가 끝나면 60분을 더해주고 마지막은 휴식이 필요하지 않기 때문에 -60으로 마무리 해준다.