문제 설명
현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.
참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.
상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.
예를 들어, 5명의 멘토가 있고 1~3번의 3가지 상담 유형이 있을 때 아래와 같은 참가자의 상담 요청이 있습니다.
참가자의 상담 요청
| 참가자 번호 | 시각 | 상담 시간 | 상담 유형 |
| 1번 참가자 | 10분 | 60분 | 1번 유형 |
| 2번 참가자 | 15분 | 100분 | 3번 유형 |
| 3번 참가자 | 20분 | 30분 | 1번 유형 |
| 4번 참가자 | 30분 | 50분 | 3번 유형 |
| 5번 참가자 | 50분 | 40분 | 1번 유형 |
| 6번 참가자 | 60분 | 30분 | 2번 유형 |
| 7번 참가자 | 65분 | 30분 | 1번 유형 |
| 8번 참가자 | 70분 | 100분 | 2번 유형 |
이때, 멘토 인원을 아래와 같이 정하면, 참가자가 기다린 시간의 합이 25로 최소가 됩니다.
| 1번 유형 | 2번 유형 | 3번 유형 |
| 2명 | 1명 | 2명 |
1번 유형
1번 유형을 담당하는 멘토가 2명 있습니다.
1번 참가자가 상담 요청했을 때, 멘토#1과 10분~70분 동안 상담을 합니다.
3번 참가자가 상담 요청했을 때, 멘토#2와 20분~50분 동안 상담을 합니다.
5번 참가자가 상담 요청했을 때, 멘토#2와 50분~90분 동안 상담을 합니다.
7번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 5분 동안 기다리고 멘토#1과 70분~100분 동안 상담을 합니다.
2번 유형
2번 유형을 담당하는 멘토가 1명 있습니다.
6번 참가자가 상담 요청했을 때, 멘토와 60분~90분 동안 상담을 합니다.
8번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 6번 참가자의 상담이 끝날 때까지 20분 동안 기다리고 90분~190분 동안 상담을 합니다.
3번 유형
3번 유형을 담당하는 멘토가 2명 있습니다.
2번 참가자가 상담 요청했을 때, 멘토#1과 15분~115분 동안 상담을 합니다.
4번 참가자가 상담 요청했을 때, 멘토#2와 30분~80분 동안 상담을 합니다.
상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ k ≤ 5
- k ≤ n ≤ 20
- 3 ≤ reqs의 길이 ≤ 300
- reqs의 원소는 [a, b, c] 형태의 길이가 3인 정수 배열이며, c번 유형의 상담을 원하는 참가자가 a분에 b분 동안의 상담을 요청했음을 의미합니다.
- 1 ≤ a ≤ 1,000
- 1 ≤ b ≤ 100
- 1 ≤ c ≤ k
- reqs는 a를 기준으로 오름차순으로 정렬되어 있습니다.
- reqs 배열에서 a는 중복되지 않습니다. 즉, 참가자가 상담 요청한 시각은 모두 다릅니다.
입출력 예
| k | n | reqs | result |
| 3 | 5 | [[10, 60, 1], [15, 100, 3], [20, 30, 1], [30, 50, 3], [50, 40, 1], [60, 30, 2], [65, 30, 1], [70, 100, 2]] | 25 |
| 2 | 3 | [[5, 55, 2], [10, 90, 2], [20, 40, 2], [50, 45, 2], [100, 50, 2]] | 90 |
| 2 | 3 | [[0, 100, 1], [5, 100, 2], [10, 100, 1], [15, 30, 2], [20, 100, 1], [45, 10, 2], [60, 5, 2]] | 270 |
문제 해설
주요 골자는 가장 효율적인 방식의 상담원을 배치하라는 의미이다.
가장 효율적인 방법의 상담원을 배치하는 방법은, 가장 최소의 상담 대기시간을 가지는 경우가 될것이고,
가장 최소의 상담 대기시간을 가지게 하려면 모든 경우의 수를 전부 대입해봐야 할 것이다. 그러나, 모든 경우의 수를 재귀형태로 돌려버리면 너무 오래 걸리게 됨으로,
한층 나아갈 때 마다 모든 경우의 수를 확인하고, 가장 효율적인 경우로 이동하는 방식의 점진적 탐색방식을 사용해야 한다.
즉, 처음 조건에서는 모든 유형에 한명 의 상담원이 배치되어야 함으로, 그렇게 배치한 뒤.
상담원을 어디에 늘릴 것 인지, 1유형에 한명 넣어보고 순환시켜보고, 2유형에 한명 넣어보고 순환시켜보고 를 반복하여. 마지막 유형까지 순환시켜 본 뒤, 가장 효율적인 위치에 상담원을 배치하여 다음단계로 넘어가게 코드를 작성해야 한다.
첫 번째 시도
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(int k, int n, vector<vector<int>> reqs)
{
int answer = 0;
vector<vector<int>> con(k+1, vector<int>(1,0));
n -= k;
int time = 0;
for (auto& def : reqs)
{
int contime = def[0] - time;
for (auto& def : con)
for (auto& chack : def)
chack -= contime;
auto&& chack_min = min_element(con[def[2]].begin(), con[def[2]].end());
if ((*chack_min) > 0 && n > 0) {
con[def[2]].push_back(def[1]);
n--;
}
else if((*chack_min) < 0)
*chack_min = def[1];
else {
answer += *chack_min;
*chack_min += def[1];
}
time += contime;
}
return answer;
}실패
우선 전체 솔루션에서 한명씩 다가오는 상담을 배치하고, 다음 상담인원이 도착했을 때, 가장 적게 남은 해당유형의 상담원에게 배치하고, 만약, 남은 상담원이 존재할경우, 그곳에 새 상담원을 배치하는 형태로 코드를 작성하였으나,
현재 가장 효율적으로 배치된 상담원이 최종적으로 가장 효율적인 형태가 아닐 수 있음을 생각하지 못했음.
두 번째 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> answer;
void greedy(vector<vector<int>> con, int nowcon, int n, const vector<vector<int>>& reqs)
{
int nowanswer = 0;
while (n > 0)
{
con[nowcon].push_back(0);
greedy(con, (nowcon + 1) % (con.size() - 1) + 1, n - 1, reqs);
n--;
}
int time = 0;
for (auto& def : reqs)
{
int contime = def[0] - time;
for (auto& def : con)
for (auto& chack : def)
chack -= contime;
auto&& chack_min = min_element(con[def[2]].begin(), con[def[2]].end());
if ((*chack_min) < 0)
*chack_min = def[1];
else {
nowanswer += *chack_min;
*chack_min += def[1];
}
time += contime;
}
answer.push_back(nowanswer);
}
int solution(int k, int n, vector<vector<int>> reqs)
{
vector<vector<int>> con(k + 1, vector<int>(1, 0));
n -= k;
for (int i = 1; i < con.size(); i++)
greedy(con, i, n, reqs);
return *min_element(answer.begin(), answer.end());
}실패
그렇다면, 깊이탐색으로 각 최종단계마다. 삼각형 모양으로, 배치하게 하여 재귀형태의 데이터유형을 만들고. 해당 데이터 유형을 탐색하게 돌려보았음.
3개의 유형이 존재할 경우, 각 유형마다 반복되는 횟수가. 다음과 같이 배치되게 코드가 작성됨.
그런데, 이 또한 가장 효율적인 데이터의 구조를 확인하지 못할 수 있다는 것을 생각하지 못함.
세 번째 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> answer;
void greedy(vector<vector<int>> con, int nowcon, int n, const vector<vector<int>>& reqs)
{
int nowanswer = 0;
while (n > 0)
{
con[nowcon].push_back(0);
for(int i = 0; i < con.size(); i++)
greedy(con, (nowcon + i) % con.size(), n - 1, reqs);
n--;
}
int time = 0;
for (auto& def : reqs)
{
int contime = def[0] - time;
for (auto& def : con)
for (auto& chack : def)
{
chack -= contime;
if(chack < 0) chack = 0;
}
auto&& chack_min = min_element(con[def[2]-1].begin(), con[def[2]-1].end());
nowanswer += *chack_min;
*chack_min += def[1];
time += contime;
}
answer.push_back(nowanswer);
}
int solution(int k, int n, vector<vector<int>> reqs)
{
vector<vector<int>> con(k, vector<int>(1, 0));
n -= k;
for (int i = 0; i < con.size(); i++) greedy(con, i, n, reqs);
return *min_element(answer.begin(), answer.end());
}실패
전방위 탐색으로 모든 경우의 수를 전부 탐색해보기로 했음, 무조건 정답이 나타나게 코드가 작성되었으나, 시간초과가 나타나 실패
네 번째 시도
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> answer;
set<vector<int>> cons;
void greedy_con(vector<int>& input, int n, int p)
{
if (n == 0) {
cons.insert(input);
return;
}
vector<int> nextinput(input);
++nextinput[p];
greedy_con(nextinput, n - 1, p);
greedy_con(nextinput, n - 1, (p + 1) % nextinput.size());
p = p - 1 <= 0 ? nextinput.size() - 1: p - 1;
greedy_con(nextinput, n - 1, p % nextinput.size());
}
void makecon(const vector<int>& I, vector<vector<int>>& output)
{
output.resize(I.size());
for (int i = 0; i < output.size(); i++)
output[i].resize(I[i], 0);
}
int solution(int k, int n, vector<vector<int>> reqs)
{
vector<int> input(k, 1);
n -= k;
vector<int> chack(input.size());
for (auto& def : reqs) chack[def[2] - 1] += def[1];
int max = 0, num = 0;
for (int i = 0; i < chack.size(); i++) {
num = max > chack[i] ? num : i;
max = max > chack[i] ? max : chack[i];
}
greedy_con(input, n, num);
greedy_con(input, n, (num + 1) % k);
num = num - 1 <= 0 ? k : num - 1;
greedy_con(input, n, (num - 1) % k);
for (auto& con_i : cons) {
vector<vector<int>> con;
makecon(con_i, con);
int nowanswer = 0;
int time = 0;
for (auto& def : reqs)
{
int contime = def[0] - time;
int* chack_min = &con[def[2] - 1][0];
for (int i = 0; i < con.size(); i++) {
for (auto& chack : con[i]) {
chack -= chack - contime < 0 ? chack : contime;
if (i == def[2] - 1) {
chack_min = *chack_min < chack ? chack_min : &chack;
}
}
}
nowanswer += *chack_min;
*chack_min += def[1];
time += contime;
}
answer.emplace_back(nowanswer);
}
return *min_element(answer.begin(), answer.end());
}실패
가장 효율적인 방식대로 코드르 작성하면, 그래도 시간초과가 나타나지 않을것 같아서 복사 대입을 최소화 하려고 코드를 정리함.
인터페이스를 정의하고, 가능한 유형의 모든 인터페이스를 제작. 제작한 인터페이스 대로 데이터를 생성하고 돌리게 한뒤. 가능한 최소한의 비교연산을 적용하기 위해 for문을 손봤음.
그래도 어림도 없지. 시간초과가 나타남
다섯 번째 시도
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
using namespace std;
int solution(int k, int n, vector<vector<int>> reqs)
{
vector<vector<int>> con_i(k, vector<int>(1, 0));
n -= k;
int wait_time = 0;
vector<int> minstruct(k);
while (n >= 0)
{
minstruct.resize(k);
for (int i = 0; i < con_i.size(); i++) {
wait_time = 0;
vector<vector<int>> con(con_i);
n > 0 ? con[i].push_back(0) : void();
for (auto& def : con) {
int c = def.size();
def.clear();
def.resize(c, 0);
}
int nowanswer = 0;
int time = 0;
for (auto& def : reqs)
{
int contime = def[0] - time;
for (auto& chacklist : con)
for (auto& chack : chacklist)
chack -= chack - contime < 0 ? chack : contime;
auto&& chack_min = min_element(con[def[2] - 1].begin(), con[def[2] - 1].end());
wait_time += *chack_min;
*chack_min += def[1];
time += contime;
}
minstruct[i] = wait_time;
if(n <- 0) break;
}
con_i[distance(minstruct.begin(), min_element(minstruct.begin(), minstruct.end()))].push_back(0);
--n;
}
return *min_element(minstruct.begin(), minstruct.end());
}성공
코드의 유형을 아예 바꿔서 하나하나 짚어가면서 코드를 연장시키게 작성함.
한 유형의 데이터를 결정하기 위해 해당 위치에서 가능한 모든 수를 계산하고. 다음단계로 넘어가게 코드를 작성하였더니 성공함.
'코딩테스트 문제 풀이 > 탐욕법' 카테고리의 다른 글
| 연속된 부분 수열의 합 (0) | 2024.04.22 |
|---|---|
| 광물 캐기 (0) | 2024.04.17 |
| 단속 카메라 (0) | 2024.02.20 |
| 섬 연결하기 (0) | 2024.02.15 |
| 구명 보트 (0) | 2024.02.15 |