[C++] 삼성 SDS KOITP 전화상담

문제링크 : https://koitp.org/problem/SDS_TEST_CONSULTING

[삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 4번 문제]

최대 상담 고객의 수 : 최소 상담시간 조건을 충족해야 한다. 수진이의 근무시간을 최소 상담시간으로 나눈 몫을 취하면 된다.

최소 상담 고객의 수 : 고객들이 원하는 상담시간 모두를 더하면 된다. 단, 수진이의 근무시간을 초과하기 전까지로 한다.

최소 ~ 최대 사이의 값으로 loop를 돌려서 값을 구하면 된다.

1. 고객 당 10점씩 받을 수 있기 때문에 고객의 수 만큼 10점씩 누적시킨다.

2. 모든 고객이 최소 시간만큼만 상담한다고 가정하고 수진이의 근무시간에서 최소 시간만큼만 뺀다.

3. 남아있는 시간을 효율적으로 사용하려면 불만족 지수를 3 -> 2 -> 1 순서로 차감 시켜주면 된다.

4. 모든 고객의 불만족 지수를 1, 2, 3 점수 별로 나누어 각 항목당 부족한 상담 시간을 합산을 한다.

5. 4의 값은 고객이 하나씩 추가될 때마다 반복해서 계산되는 부분이다. 따라서 첫번째 연산시에는 0 ~ minNum 까지 루프를 돌리지만 그 다음 루프인 0 ~ minNum + 1 부터는 0 ~ minNum 까지의 값이 어짜피 중복되므로 minNum ~ minNum + 1 구간만 새로 추가해주면 되기 때문에 이전 루프에서 계산했던 값들을 그대로 활용한다. 이렇게 하기 위하여 루프 바깥에 time1, time2, time3를 선언하였고 idx 변수를 for문에서 초기값을 그대로 사용하는 것을 확인할 수 있다.

6. 최소 상담시간을 제외한 나머지 모든 시간을 일단 전부 빼준다. (2~4에서 구한 값들을 활용하여)

7. 남아있는 시간 만큼 다시 3 -> 2 -> 1 순서로 더해준다.

8. 누적된 값이 이전 루프에서 받았던 점수보다 큰지 작은지 비교하여 계산한다.

매 루프시마다 for문을 N회 실행하지 않고 최초 loop에서만 for문을 N회 실행 후 이후 loop에선 1회만 실행하여 시간을 줄였다.

// KOITP_SDS_Atype_04
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    // freopen("../input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int num;
        int minTime;
        int workTime;
        int score = 0;
        int temp = 0;
        int remain;
        cin >> num >> minTime >> workTime;
        vector<vector<int>> data(num, vector<int>(2));
        for(int i = 0; i < num; i++)
            cin >> data[i][0] >> data[i][1];
        int maxNum = min(workTime / minTime, num);
        int minNum = 0;
        int tmptmp = 0;
        for(int i = 0; i < maxNum; i++) {
            tmptmp += data[i][0];
            if(tmptmp < workTime)
                minNum++;
            else
                break;
        }
        int time1 = 0, time2 = 0, time3 = 0;
        int idx = 0;
        for(num = minNum; num <= maxNum; num++){
            temp = 10*num;
            remain = workTime - minTime * num;
            for(idx; idx < num; idx++){
                if(data[idx][1] == 1)
                    time1 += data[idx][0] - minTime;
                else if(data[idx][1] == 2)
                    time2 += data[idx][0] - minTime;
                else
                    time3 += data[idx][0] - minTime;
            }
            temp -= time1 + time2 * 2 + time3 * 3;
            if(remain > time3){
                temp += time3 * 3;
                remain -= time3;
            }
            else{
                temp += remain * 3;
                score = max(temp, score);
                continue;
            }
            if(remain > time2){
                temp += time2 * 2;
                remain -= time2;
            }
            else{
                temp += remain * 2;
                score = max(temp, score);
                continue;
            }
            if(remain > time1){
                temp += time1;
                remain -= time1;
                if(remain >= minTime)
                    continue;
            }
            else{
                temp += remain * 1;
            }
            score = max(temp, score);
        }
 
        cout << "#" << t+1 << " " << score << "\n";
    }
    return 0;
}