문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 정렬
오늘은 선영이의 생일이다. 선영이의 친구들은 선영이에게 생일선물로 스타크래프트 2를 사주기로 했다.
선영이의 친구들은 비용을 공정하게 내기로 결정했다. 친구들 중 일부는 다른 친구들보다 돈이 많기 때문에, 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않기로 했다. 모든 사람이 내는 돈은 1원의 배수이다. 즉, 분수로 낼 수는 없다.
친구들은 자신이 낼 수 있는 최대 금액을 적어서 냈다. 이제 이 정보를 이용해서 각자 낼 금액이 얼마인지 계산해보려고 한다.
공정하게 선물 비용을 내려면, 선물 금액의 1/n과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다. 만약, 같은 경우가 나오는 경우에는 두 번째 차이의 최댓값을 최소로 해야 하고, 이런 식이다. 각 사람이 낼 수 있는 최소 금액은 1원이기 때문에, 금액을 분배하는 방법이 여러 가지가 나올 수 있다. 이 경우에는 돈을 많이 낼 수 있는 사람이 더 내게 된다. 그래도 여러 가지라면, 리스트의 앞에 있는 사람이 돈을 더 낸다.
선영이의 친구들이 낼 수 있는 금액과 선물의 금액이 주어졌을 때, 각자 얼마를 내야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 선물의 가격 p (1 ≤ p ≤ 1,000,000)와 선영이 친구의 수 n (2 ≤ n ≤ 100) 이 주어진다. 둘째 줄에는 각 사람이 낼 수 있는 금액 ai (1 ≤ ai ≤ 1,000,000) 가 주어진다.
출력
각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.
풀이
친구들이 선물을 사기 위해서 최대한 공정하게 돈을 내야한다.
최대한 공정하게라는 말은 p / n - 각 사람이 낸 금액의 차이의 최댓값을 최소로 만드는 것이다.
그러한 경우가 여러 개라면 그 다음 최댓값을 최소로 만들고, 이를 반복한다.
쉽게 말하자면, p = 20, n = 4일 때 20 / 4 = 5이다.
이때 최적해는 5 5 5 5이고, 최대한 이렇게 만드는 것이 공정하다는 뜻이다.
그래서 나는 초기에는 각 친구가 지불한 금액을 p / n으로 설정해 줬다. 이때 p / n보다 낼 수 있는 금액이 없다면 모든 돈을 지불해야 한다. 그래야 공정하다.
다음 문제의 조건을 보자,
분배할 때 여러 경우의 수가 나올 수 있다. 그래서 돈을 많이 낼 수 있는 사람이 더 내고, 그러한 경우도 여러 가지라면 리스트의 앞에 있는 사람이 돈을 더 내야 한다고 한다.
이 조건은 정렬 조건이며, 나는 낼 수 있는 금액을 기준으로 내림차순 해주고, 같은 경우에는 리스트 순서를 기준으로 오름차순 해줬다.
친구 리스트가 조건에 맞게 정렬되어 있다면, 이제 앞에서부터 순차적으로 1씩 지불한다.
만약 지불하지 못하는 경우를 만나면 그 뒤는 탐색하지 않아도 된다. 그래서 다시 cursor를 0으로 조정하고 앞에서부터 다시 1씩 지불한다.
그리고 전체 지불한 금액이 p가 될 때까지 반복한다.
(만약 돈을 가장 많이 지불할 수 있는 친구(인덱스 0)의 금액이 0이되면 이 경우에도 반복을 멈추고, IMPOSSIBLE을 출력하면 된다.)
마지막으로 리스트 순으로 다시 정렬하고 출력해 주면 된다.
시간 복잡도는 케이스마다 O(p)다.
소스 코드
import java.io.*;
import java.util.*;
class Info implements Comparable<Info> {
int ind, max, pay;
Info(int ind, int max, int pay) {
this.ind = ind;
this.max = max;
this.pay = pay;
}
@Override
public int compareTo(Info o) {
if(this.max < o.max) {
return 1;
} else if(this.max > o.max) {
return -1;
} else {
if(this.ind < o.ind) {
return -1;
} else if(this.ind > o.ind) {
return 1;
}
}
return 0;
}
}
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0; i<T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int bestP = p / n;
Info[] fList = new Info[n];
StringTokenizer st2 = new StringTokenizer(br.readLine());
int totalPay = 0;
for(int j=0; j<n; j++) {
int max = Integer.parseInt(st2.nextToken());
fList[j] = new Info(j, max, max >= bestP ? bestP : max);
totalPay += fList[j].pay;
}
int leftP = p - totalPay;
Arrays.sort(fList);
int cursor = 0;
while(leftP != 0) {
if(cursor == fList.length || fList[cursor].max - fList[cursor].pay == 0) {
if(cursor == 0) {
break;
}
cursor = 0;
continue;
}
fList[cursor].pay += 1;
leftP -= 1;
cursor += 1;
}
if(leftP != 0) {
sb.append("IMPOSSIBLE").append("\n");
} else {
Arrays.sort(fList, new Comparator<Info>() {
@Override
public int compare(Info f1, Info f2) {
return Integer.compare(f1.ind, f2.ind);
}
});
for(int k=0; k<fList.length; k++) {
sb.append(fList[k].pay).append(" ");
}
sb.append("\n");
}
}
System.out.println(sb.toString().trim());
}
}