1 - 문제
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 선물의 가격 p (1 ≤ p ≤ 1,000,000)와 선영이 친구의 수 n (2 ≤ n ≤ 100) 이 주어진다. 둘째 줄에는 각 사람이 낼 수 있는 금액 ai (1 ≤ ai ≤ 1,000,000) 가 주어진다.
출력
각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.
예제 입력
3 20 4 10 10 4 4 7 3 1 1 4 34 5 9 8 9 9 4
예제 출력
6 6 4 4 IMPOSSIBLE 8 7 8 7 4
2 - 분석
조건1
공정하게 선물 비용을 내려면, 선물 금액의 1/n 과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다.
- 각각의 사람들이 최대한 비슷한 값을 내도록 해야 함.
- 선물 금액의 1/n 보다 최대로 낼 수 있는 금액이 적은 사람은 개인 최대 금액을 모두 지불해야 함.
조건2
2-1 : 돈을 많이 낼 수 있는 사람이 더 내게 된다.
2-2 : 그래도 여러 가지라면, 리스트의 앞에 있는 사람이 돈을 더 낸다.
예제의 3번째 테스트 케이스와 같이 선물의 가격이 34원, 친구 5명이고 각각 9원, 8원, 9원, 9원, 4원 을 최대로 지불할 수 있다고 할 때,
조건1에 맞게 금액을 정하면 금액이 큰 순서대로 8원, 8원, 7원, 7원, 4원 이 된다.
조건2-1가 성립하기 위해서는 최대 금액이 9원인 친구 두명이 8원을 지불해야 한다.
또한, 조건2-2가 성립하려면 최대 금액인 9원인 세 명의 친구 중 한명이 7원을 내야하는 상황에서 리스트의 맨 앞 친구가 가장 많은 금액을 지불해야 하므로 아래의 이미지와 같은 상황은 정답이 될 수 없다.
3 - 풀이
최대 금액을 오름차순으로 정렬하되, 입력 순서대로 낼 수 있는 금액을 출력해야 하므로, 정렬 후에도 입력 순서를 기억할 수 있도록 2차원 배열을 사용한다.
int[][] maxCost = new int[n][2]; for (int i = 0; i < n; i++) { maxCost[i][0] = Integer.parseInt(st.nextToken()); maxCost[i][1] = i; }
모든 사람의 최대 금액 총합이 선물의 가격보다 적을 경우 선물을 구입할 수 없으므로, 해당 테스트케이스는 "IMPOSSIBLE" 을 입력하고 continue 한다.
int sum = 0; for (int i = 0; i < n; i++) { sum += maxCost[i][0]; } if (sum < p) { sb.append("IMPOSSIBLE\n"); continue; }
최대 금액의 오름차순으로 정렬한다. 최대 금액이 같을 경우 입력 순서의 내림차순으로 정렬한다. 최대한 공평하게 분배 후에 남은 금액이 있을 경우 배열 역순으로 그 금액을 재분배 할 예정이므로 입력 순서의 내림차순 정렬을 한다.
Arrays.sort(maxCost, (x, y) -> { if (x[0] != y[0]) { return Integer.compare(x[0], y[0]); } return Integer.compare(y[1], x[1]); });
결과를 담을 배열 result를 선언하고, remain 에는 선물의 금액을 대입한다.
지불 가능한 최대 금액과 현재 남은 금액 / 남은 인원 중에서 더 작은 값을 지불한다.
매 차례 1/n 과 가장 가까운 금액을 지불하고, curIdx 를 활용하여 입력 순서대로 결과 배열에 담는다.
int[] result = new int[n]; int remain = p; for (int i = 0; i < n; i++) { if (remain == 0) break; int curIdx = maxCost[i][1]; result[curIdx] = Math.min(maxCost[i][0], remain / (n - i)); remain -= result[curIdx]; }
배열을 순회한 이후, 남은 금액이 있을 경우 배열 역순으로 남은 금액을 낼 수 있는 만큼 추가적으로 더 낸다.
if (remain > 0) { for (int i = n - 1; i >= 0 && remain > 0; i--) { int curIdx = maxCost[i][1]; int additional = Math.min(maxCost[i][0] - result[curIdx], remain); result[curIdx] += additional; remain -= additional; } }
그럼에도 남아 있는 금액이 있는 경우, "IMPOSSIBLE" 을 입력하고 그렇지 않은 경우는 result 배열의 결과를 입력한다.
if (remain > 0) { sb.append("IMPOSSIBLE\n"); } else { for (int i = 0; i < n; i++) { sb.append(result[i]).append(" "); } sb.append("\n"); }
🔗 전체 코드
