해답 1
#include <iostream>
void arraySort(int *arr, int start, int end) {
if (end - start < 1) return;
if (end - start == 1) {
if (arr[start] <= arr[end]) return;
else {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
return;
}
}
int pivot = arr[start];
int *sp = &arr[start];
int *ep = &arr[end];
int pp = start;
while (start < end) {
while (*sp < pivot) {
sp++;
pp++;
}
while (*ep >= pivot) ep--;
if (sp >= ep) break;
int temp = *sp;
*sp = *ep;
*ep = temp;
}
if(pp==start) arraySort(arr, pp + 1, end);
else {
arraySort(arr, start, pp - 1);
arraySort(arr, pp, end);
}
}
int main() {
int T, N, P;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
scanf("%d %d", &N, &P);
int leastCoach = -1;
int *coach = new int[N];
int *skill = new int[N];
for (int j = 0; j < N; j++) {
scanf("%d", &skill[j]);
}
arraySort(skill, 0, N - 1);
for (int j = 1; j < N; j++) {
coach[j] = skill[j] - skill[j - 1];
if (j < P - 1) continue;
int sum = 0;
for (int k = 0; k < P - 1; k++) {
sum += coach[j - k] * (P - k - 1);
}
if (sum < leastCoach || leastCoach == -1) leastCoach = sum;
}
printf("Case #%d: %d\n",i+1, leastCoach);
}
}
1. 선수들의 스킬을 오름차순으로 정렬한다.
2. 인접한 선수들간의 스킬 차를 coach 배열에 저장
3. coach 배열을 순회하며 트레이닝 최소값을 구한다.
해답 2
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
int main() {
int T, N, P;
int *skill = new int[10001];
scanf("%d", &T);
for (int i = 0; i < T; i++) {
scanf("%d %d", &N, &P);
int leastCoach = -1;
std::deque<int> team;
for (int j = 10000; j > 0; j--) skill[j] = 0;
for (int j = 0; j < N; j++) {
int sk;
scanf("%d", &sk);
skill[sk]++;
}
for (int j = 10000; j > 0; j--) {
for (int k = 0; k < skill[j]; k++) {
team.push_back(j);
}
if (team.size() < P) continue;
while (team.size() >= P) {
int large = team[0];
int sum = 0;
for (int k = 1; k < P; k++) {
sum += large - team[k];
}
if (sum < leastCoach || leastCoach == -1) leastCoach = sum;
while (team.size()!=0 && team.front() == large) {
team.pop_front();
}
}
}
printf("Case #%d: %d\n", i + 1, leastCoach);
}
}
1. 선수들의 스킬이 최대 10000이므로 길이가 10001인 배열을 준비하고 스킬값을 입력 받을때 배열의 스킬번째 값을 1씩 증가시켜준다.
2. 큐를 생성한후, 배열의 10000번째 원소부터 순회하며 P만큼의 원소가 들어올때 까지 큐에 스킬값을 쌓는다.
(C++의 queue는 임의 접근이 불가능하기 때문에 deque를 사용)
3. 큐에 원소가 쌓이면 P개 만큼의 원소에 대해 같은 값을 갖게하는 트레이닝값을 구하고 최소값을 갱신한다.
4. 큐의 가장큰 원소와 같은 값을 가지는 원소를 모두 제거한다. 이후 2를 계속.
'문제 풀기 > 기타 문제' 카테고리의 다른 글
| KickStart 2019 Round C - Wiggle Walk (0) | 2019.05.27 |
|---|