Google Kick Start 2019 Round A _ problem A : Training

 

이 글은 한국 시간으로 2019년 3월 24일 오후 1시에 치뤄진  Google Kick Start 2019 Round A에 나온 문제에 대해서 다룹니다.

 

 

problem A : Training

---

 

Q. 한 학교의 축구 코치로서 N명의 선수 중 대표 P명을 선발해야 한다. P명의 선수를 선발할 때, P명 모두 실력이 같아야한다. 한 시간에 한 명씩 트레이닝할 수 있으며 트레이닝 받은 선수는 실력이 1씩 오른다. 이 때, P명의 선수를 선발하는 데 걸리는 최소 시간을 구하시오. 단, 처음 선수들의 실력은 입력으로 주어진다.

 

저는 선수들의 실력을 배열에 저장해 정렬한 후 P번 선수부터 n번 선수까지 기준 실력으로 했을 때, 필요한 시간들을 비교해 최소 시간을 구하는 식으로 방향을 잡았습니다. 

정렬을 하는 이유는 기준 실력 아래의 선수 p-1명의 선수들이 그 기준 실력에 대해 최소시간이 요구되는 선수들이기 때문입니다. 

모든 선수들이 가져야할 실력은 (기준 실력 * P) 입니다. 

실력 1을 올리기 위해 1시간이 필요하므로 선수들이 기준 실력이 되기위해 필요한 시간은 (기준실력 - 현재실력) 입니다. 

x번째 선수가 기준실력인 팀이 되기 위해 필요한 최소 트레이닝 시간은 (기준실력 - x-p-1번째 선수 실력) + ..... +  (기준실력 - x-1번째 선수 실력) +  (기준실력 - x번째 선수 실력)이 되겠습니다.

위의 식을 정리하면, (기준 실력 * p) - (x-p-1번째 선수의 실력부터 x번째 선수의 실력의 합) 이라는 점화식이 나옵니다.

x번째 선수는 트레이닝할 시간이 필요없으므로 제외시킨다면 (기준 실력 * p - 1) - (x-p-1번째 선수의 실력부터 x -1 번째 선수의 실력의 합)이라고 할 수 있겠네요.

 

예제) n = 6, p = 4, 선수들 실력 = 5 5 1 2 3 4

 

(1) 실력들을 정렬 => 1 2 3 4 5 5

(2) 4번째 선수의 실력 부터 6번째 선수의 실력을 기준으로 설정.

 

1 2 3 4 5 5 => 4 * 3 - (1 + 2 + 3) = 6

1 2 3 4 5 5 => 5 * 3 - (2 + 3 + 4) = 6

1 2 3 4 5 5 => 5 * 3 - (3 + 4 + 5) = 3

 

n과 p가 커지면, (x-p-1번째 선수의 실력부터 x -1 번째 선수의 실력의 합)을 반복문을 통해 구할 때 시간을 많이 잡아먹습니다.

 

이를 방지하기 위해, 

1) 첫번째, 총합만 반복문을 통해 구합니다.

2) 기준 실력이 바뀔 때, 맨 첫번째 실력을 빼고 마지막 다음의 실력을 더하면서 기준이 바뀔때 마다 반복문을 사용하는 것을 방지합니다.

 

1 2 3 4 5 5 => 반복문을 통해 총합 6을 구함.

1 2 3 4 5 5 => 6에서 1을 빼고 4를 더함 => 9

1 2 3 4 5 5 => 9에서 2를 빼고 5를 더함 => 12

 

이런 과정에서 최소값을 구하면 정답을 찾을 수 있습니다!

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
 
using namespace std;
 
int s[10000];
 
int main() {
    int T;
    int idx = 0;
 
    cin >> T;
 
    while (idx++ < T) {
        int n, p;
        int minimum = 1000000;
 
        cin >> n >> p;
 
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }
 
        sort(s, s + n);
 
        int sum = 0;
 
        for (int i = 0; i < p - 1; i++) { // 첫번째 총합
            sum += s[i];
        }
 
        minimum = s[p - 1] * (p - 1) - sum;
 
        for (int i = p; i < n; i++) { 
            sum = sum - s[i - p] + s[i - 1]; // 총합을 구하는 식
            int total = s[i] * (p - 1); // 팀을 꾸리기 위한 전체의 실력의 합
            minimum = min(minimum, total - sum); 
        }
 
        cout << "Case #" << idx << ": " <<minimum << endl;
    }
}

 

 

처음으로, 문제풀이 글을 작성했는데, 처음인지라 많이 어색하고 너무 구구절절 설명하지 않았나 생각이 드네요(머쓱;;)

 

다른 의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!