생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 3661번 생일 선물

생각중임 2024. 4. 14. 19:06

생일 선물

문제 설명

오늘은 선영이의 생일이다. 선영이의 친구들은 선영이에게 생일선물로 스타크래프트 2를 사주기로 했다.

선영이의 친구들은 비용을 공정하게 내기로 결정했다. 친구들 중 일부는 다른 친구들보다 돈이 많기 때문에, 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않기로 했다. 모든 사람이 내는 돈은 1원의 배수이다. 즉, 분수로 낼 수는 없다.

친구들은 자신이 낼 수 있는 최대 금액을 적어서 냈다. 이제 이 정보를 이용해서 각자 낼 금액이 얼마인지 계산해보려고 한다.

공정하게 선물 비용을 내려면, 선물 금액의 1/n과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다. 만약, 같은 경우가 나오는 경우에는 두 번째 차이의 최댓값을 최소로 해야 하고, 이런 식이다. 각 사람이 낼 수 있는 최소 금액은 1원이기 때문에, 금액을 분배하는 방법이 여러 가지가 나올 수 있다. 이 경우에는 돈을 많이 낼 수 있는 사람이 더 내게 된다. 그래도 여러 가지라면, 리스트의 앞에 있는 사람이 돈을 더 낸다.

선영이의 친구들이 낼 수 있는 금액과 선물의 금액이 주어졌을 때, 각자 얼마를 내야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 선물의 가격 p (1 ≤ p ≤ 1,000,000)와 선영이 친구의 수 n (2 ≤ n ≤ 100) 이 주어진다. 둘째 줄에는 각 사람이 낼 수 있는 금액 ai (1 ≤ ai ≤ 1,000,000) 가 주어진다.

출력

각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.

제한사항

  • 없음

입출력 예

input return
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

문제 분석

선물의 가격 P, 친구의 수 N, 각 친구들이 낼 수 있는 금액 A가 주어진다.

선물을 구매가 불가능한 경우는 친구들의 금액의 합이 선물 가격보다 적다면 선물을 구매를 할 수가 없다.

또한, 선물의 가격과 친구들의 금액의 합이 같을 경우는 전원 모든 금액을 부담해야 한다.

공정하게 비용을 내는 조건은 3가지에서 알 수 있는 내용이 있다.

  1. 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않는다.
    • 금액 부담에 제한을 줘야 한다.
  2. 선물 금액의 1/N과 금액의 차이의 최댓값을 최소로 해야 한다.
    • 1/N의 금액을 기본적으로 부담을 해야 한다.
    • 금액을 많이 낼 수 있는 친구부터 더 비용을 부담해야 한다.
  3. 금액을 분배하는 동일한 방법이 나온다면 리스트의 앞에 있는 사람이 돈을 더 낸다.
    • 각 친구의 금액 입력의 순서를 기억하고 활용해야 한다.

먼저 1/N 금액으로 비용부담을 하고 남은 선물의 가격을 금액이 많이 낼 수 있는 친구부터 비용을 적용하기 위해 정렬을 하되, 기존의 순서를 알 수 있어야 한다.

정렬시킨 값들에 비용을 부담할 수 있는 금액에 여유가 있다면, 추가적으로 비용을 누적시키면서 선물의 가격을 채워주고 다시 원래의 순서로 변환해 출력을 해주면 될 것이다.

손으로 풀기

  1. 테스트 케이스 수를 받아 반복을 한다.
  2. 선물의 가격과 친구의 수를 입력받는다.
  3. 친구의 수만큼 반복을 하면서 한도 금액을 배열에 넣어주고 한도 금액의 총합을 구해준다.
  4. 선물의 가격과 한도 금액의 총합을 비교한다.
    • 같을 경우, 입력받은 한도 금액들을 출력하고 다음 테스트 케이스로 넘어간다.
    • 선물의 가격보다 적을 경우, IMPOSSIBLE을 출력하고 다음 테스트 케이스로 넘어간다.
  5. 선물의 1/N금액과 한도 금액을 비교해 적은 금액과 인덱스 정보를 2차 배열로 초기화해 주고 부담한 금액을 선물 가격에서 감소시킨다.
  6. 부담하고 있는 비용배열을 인덱스 정보를 이용해 한도 금액을 기준으로 내림차순 정렬을 해준다.
  7. 남은 선물의 가격이 0이 될 때까지 부담한 금액 배열을 반복한다.
    • 부담한 금액이 한도 금액보다 적으면 선물의 가격을 1 감소시키고 부담 금액을 1 증가시킨다.
    • 선물의 가격이 0이 되면 종료한다.
  8. 부담한 금액을 인덱스 정보를 기준으로 다시 정렬해 주고 출력을 해준다.

나의 문제풀이

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder stringBuilder = new StringBuilder();

        // 테스트 케이스의 수
        int T = readNumber();

        for (int i = 0; i < T; i++) {
            // 선물의 가격
            int P = readNumber();
            // 친구의 수
            int N = readNumber();

            // 친구들의 한도 금액
            int total = 0;
            int[] moneys = new int[N];
            for (int j = 0; j < N; j++) {
                moneys[j] = readNumber();
                total += moneys[j];
            }

            // 친구 전원의 금액 합이 선물 가격보다 적으면 살 수 없다.
            if (total < P) {
                stringBuilder.append("IMPOSSIBLE").append("\n");
                continue;
            } else if (total == P) {
                for (int money : moneys) {
                    stringBuilder.append(money).append(" ");
                }
                stringBuilder.append("\n");
                continue;
            }

            // 선물의 1/n 금액
            int fairCost = P / N;

            // 기본 금액 계산
            int[][] costs = new int[N][2];
            for (int j = 0; j < N; j++) {
                // 현재 사람이 가진 돈과 기본 금액 중 작은 값을 선택하여 부담 금액으로 설정
                costs[j][0] = Math.min(fairCost, moneys[j]);
                // 기존의 위치 정보
                costs[j][1] = j;

                // 선물 비용에서 현재 사람의 부담 금액을 빼줌
                P -= costs[j][0];
            }

            // 돈을 많이 가지고 있는 순으로 정렬
            Arrays.sort(costs, (o1, o2) -> moneys[o2[1]] - moneys[o1[1]]);

            // 남은 선물 비용을 금액이 많은 사람부터 추가 누적
            while (P > 0) {
                for (int j = 0; j < N; j++) {
                    if (moneys[costs[j][1]] > costs[j][0]) {
                        costs[j][0]++;
                        P--;
                    }

                    if (P == 0) break;
                }
            }

            // 다시 위치순으로 정렬
            Arrays.sort(costs, (o1, o2) -> o1[1] - o2[1]);

            for (int[] cost : costs) {
                stringBuilder.append(cost[0]).append(" ");
            }
            stringBuilder.append("\n");
        }

        System.out.println(stringBuilder);
    }

    private static int readNumber() throws IOException {
        int cur = System.in.read() & 15;
        int next = 0;
        boolean flag = cur == 13;
        if (flag) cur = 0;
        while ((next = System.in.read()) > 32) cur = (cur * 10) + (next & 15);
        return flag ? -cur : cur;
    }
}

그리디 알고리즘을 이용해서 푸는 문제들은 특정 유형으로 정리하기가 힘든 것 같다. 부분적으로 최적의 선택을 할 수 있도록 만드는 방법이 사람들의 풀이마다 차이가 많았다. 나름의 우선순위로 적용할 수 있는 방법을 찾고 구현하는 조건을 놓치지 않는다면 대부분은 성공하는 것 같다. 생각보다 다이나믹 프로그래밍보다 시간초과나 메모리 초과가 안 나오는 듯하다.

알고리즘 분류

  • 그리디 알고리즘
  • 정렬

문제 출처 - https://www.acmicpc.net/problem/3661

 

3661번: 생일 선물

각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.

www.acmicpc.net