문제

https://school.programmers.co.kr/learn/courses/30/lessons/214288

아이디어1

멘토를 유형 별 분류할 수 있는 모든 경우를 찾자

- 양의 정수 n을 양의 정수 k 개의 양의 정수들의 합으로 
표현할 수 있는 방법 (n >= k)
- 순서가 다르면 다른 것으로 취급

• DFS를 이용한 완전 탐색
• 양의 정수들의 합이기 때문에 최소가 1
  • n-k의 합을 음이 아닌 정수들의 합으로 표현하면 쉬움
• 배열의 첫번째 자리에 0부터 n-k까지 채움
  • 채우고 남은 합으로 나머지 자리를 채움
  • 마지막 자리는 나머지 합

예시) n = 5, k = 3 => sum = 2, k = 3
#
< 첫 번째 자리가 0 >
	< 두 번째 자리가 0 >
		< 세 번째 자리가 2> 0 0 2
    < 두 번째 자리가 1 >
    	< 세 번째 자리가 1> 0 1 1
    < 두 번째 자리가 2 >
    	< 세 번째 자리가 0> 0 2 0
< 첫 번째 자리가 1 >
	< 두 번째 자리가 0 >
		< 세 번째 자리가 1> 1 0 1
    < 두 번째 자리가 1 >
    	< 세 번째 자리가 0> 1 1 0
< 첫 번째 자리가 2 >
	< 두 번째 자리가 0 >
		< 세 번째 자리가 0> 2 0 0

저는 인덱스로 사용했기 때문에 이 결과를 썼습니다.
개수가 필요하면 삽입할 때 1을 더해서 삽입하면 됩니다.

그러면 결과는
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
#
총 6가지가 나옵니다.

void DFS(int sum, int k, vector<int> numbers, vector<vector<int>>& orders)
{
    if (k == 1)
    {
        numbers.push_back(sum);
        orders.push_back(numbers);
        return;
    }
    
    for (int i = 0; i <= sum; ++i)
    {
        numbers.push_back(i);
        DFS(sum - i, k - 1, numbers, orders);
        numbers.pop_back();
    }
    
}

vector<vector<int>> get_orders(int n, int k)
{
    int sum = n - k;
    vector<vector<int>> orders;
    
    vector<int> numbers;
    DFS(sum, k, numbers, orders);
    
    return orders;
}

아이디어2

유형별 멘토 수에 따른 대기 시간을 측정

• 사실 완전 탐색하기 싫어서 DP로 풀 수 있지 않을까 해서 구함

	// mt에 각 유형별 인덱스를 저장
    vector<vector<int>> mt(k); // mentee

    for (int i = 0; i < reqs.size(); ++i)
        mt[reqs[i][2] - 1].push_back(i);

    vector<vector<int>> wt; // waiting time

    for (int i = 0; i < k; ++i)
    {
        vector<int> wait = calWait(mt[i], reqs, n);
        wt.push_back(wait);
    }

테이블 구하는 함수 >>

int calTime(const vector<int>& mt, const vector<vector<int>>& reqs, const int& numMentor)
{
    int time = 0;
    vector<int> endTime;
    
    if (mt.size() < numMentor)
        return 0;
    
    for (int i = 0; i < numMentor; ++i)
        endTime.push_back(reqs[mt[i]][0] + reqs[mt[i]][1]);
    
    sort(endTime.begin(), endTime.end(), greater<int>());
    
    for (int i = numMentor; i < mt.size(); ++i)
    {
        int end = 0;
        if (endTime.back() > reqs[mt[i]][0])
        {
            time += endTime.back() - reqs[mt[i]][0];
            end = endTime.back() + reqs[mt[i]][1];
        }
        else
            end = reqs[mt[i]][0] + reqs[mt[i]][1];
            
        endTime.pop_back();
        
        endTime.push_back(end);
        sort(endTime.begin(), endTime.end(), greater<int>());
    }
    
    return time;
}

vector<int> calWait(const vector<int>& mt, const vector<vector<int>>& reqs, const int& n)
{
    vector<int> wait;
    
    for (int i = 0; i < n; ++i)
    {
        int time = calTime(mt, reqs, i + 1);
        wait.push_back(time);
    }
    
    return wait;
}

결과 >>

입출력 예 #1
vector<vector<int>> reqs = {{10, 60, 1}, {15, 100, 3}, {20, 30, 1}, {30, 50, 3}, {50, 40, 1}, {60, 30, 2}, {65, 30, 1}, {70, 100, 2}};
solution(3, 5, reqs);

>>>
175 5 0 0 0 
20 0 0 0 0 
85 0 0 0 0 

입출력 예 #2
vector<vector<int>> reqs = 	{{5, 55, 2}, {10, 90, 2}, {20, 40, 2}, {50, 45, 2}, {100, 50, 2}};
solution(2, 3, reqs);

>>>
0 0 0 
455 90 10 

최소를 구하는 함수 >>

• n = 1, k = 1 이고 300명이 0분에 도착, 100분 상담이면 (100 + 29,900) * 299 / 2 = 4,485,000
• min 초기화를 500만 이상으로 해야 통과

int get_min(const vector<vector<int>>& wt, const vector<vector<int>>& orders)
{
    int min = 10000000;
    
    for (int i = 0; i < orders.size(); ++i)
    {
        int sum = 0;
        
        for (int j = 0; j < orders[i].size(); ++j)
            sum += wt[j][orders[i][j]];
            
        min = sum < min ? sum : min;
    }
    
    return min;
}


입출력 예 #1의 경우
2 1 2일 때 합이 25로 최소

입출력 예 #2의 경우
1 2일 때 합이 90으로 최소

마무리

• 어차피 완전탐색할 거면 그냥 구해도 되지 않았나 싶음
• priority_queue 사용하면 편할 듯
• 파이썬이면 combinations_with_replacement, permutation으로 더 쉽게 가능할 듯