1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    // 벡터를 뒤집어 큐처럼 사용
    reverse(progresses.begin(), progresses.end());
    reverse(speeds.begin(), speeds.end());

    // 우선순위 큐를 사용해서 우선순위 값이 낮을수록 먼저 수행 (빨리 되는 것부터)
    // 우선순위 값은 (100 - 진행도) / 속도
    auto cmp = [&](int a, int b) -> bool
    {
        return (100 - progresses[a]) / speeds[a] > (100 - progresses[b]) / speeds[b];
    };

    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

    // 작업을 우선순위 큐에 넣기
    for (int i = 0; i < progresses.size(); ++i)
    {
        pq.push(i);
    }

    // 큐에서 꺼내서 작업 진도를 채우기
    // 작업 진도를 채우는 양은 (100 - 작업량) / 속도 만큼씩 모든 작업 채우기
    // 만약 채운 후에도 해당 인덱스가 완료되지 않았다면 1회 더 채운다
    // 이후 조건 검사, 조건이 맞다면 뒤에서부터 100인 것들을 빼낸다
    // 이걸 반복한다
    // 우선순위 큐에서 빼낼 때 vector size() 검사로 유효 인덱스인지 체크 작업 필요
    while (!pq.empty())
    {
        int idx = pq.top();
        pq.pop();

        int length = progresses.size();

        // 인덱스 유효성 검사 수행
        if (idx >= length) continue;

        // 현재 뽑은 인덱스가 꽉 차게끔 수행
        int calcCount = (100 - progresses[idx]) / speeds[idx];

        // 꽉 채우지 못하면 1회 더 수행함
        if (progresses[idx] + calcCount * speeds[idx] <= 100) ++calcCount;

        printf("idx: %d, calcCount: %d\n", idx, calcCount);

        for (int i = 0; i < length; ++i)
        {
            // 작업 진도를 한번에 채운다
            progresses[i] = min(100, progresses[i] + calcCount * speeds[i]);
            printf("p: %d\n", progresses[i]);
        }

        // 끝부분부터 100인 원소만 빼낸다
        int count = 0;
        for (int i = length - 1; i >= 0; --i)
        {
            if (progresses[i] < 100) break;

            progresses.pop_back();
            speeds.pop_back();
            ++count;
        }

        // 빼낸 적 있다면 이번 루프에서 빼낸 횟수를 answer에 기록
        if (count > 0) answer.push_back(count);
    }

    return answer;
}