백준 5911 - 선물 (자바 - 그리디)

https://www.acmicpc.net/problem/5911

5911번: 선물

 

* 문제 요약

군대에 가기 전까지 자신과 놀아준 친구 N (1 <= N <= 1,000) 명에게 선물을 주려고 한다.

돈을 B (1 <= B <= 1,000,000,000) 원 가지고 있다.

i 번째 친구가 받고 싶어하는 선물의 가격은 P(i) 원 이고, 배송비는 S(i) 원이다.

즉, i 번째 친구에게 선물을 보내려면 돈이 P(i) + S(i) 원 필요하다.

물건 가격을 절반으로 할인 받을 수 있는 쿠폰을 하나 가지고 있다. 이 쿠폰을 i 번째 친구에게 사용한다면 (P(i) / 2) + S(i) 원만 있으면 선물을 보낼 수 있다.

선물을 최대 몇 명에게 보낼 수 있는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 N 과 B 가 주어진다.

둘째 줄부터 N 개 줄에는 P(i) 와 S(i) 가 주어진다. (0 <= P(i), S(i) <= 1,000,000,000)

 

* 출력

첫째 줄에 선물을 최대 몇 명에게 보낼 수 있는지 출력한다.

 

* 예시

 

* 해결 과정

매 반복마다 현재 반값 할인을 적용할 선물과 그렇지 않을 선물 각각의 총 비용을 배열에 저장한다.

그 다음 배열을 오름차순 정렬해주고, 비용이 적게드는 선물 부터 순서대로 현재 가진 돈 B 안에서 살 수 있는지 검증한다.

반복을 통해 각 선물들을 구매하다가 다음 선물을 살 비용이 부족해지면 지금까지 구매한 선물 갯수와 이전의 반복에서 다른 선물에 반값 할인을 적용시켜서 구매 가능했던 총 선물 갯수와 비교해서 더 큰값을 저장해주는 방식으로 최종적인 최대값을 찾았다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int count = Integer.parseInt(input[0]);
        int money = Integer.parseInt(input[1]);

        Friend[] friends = new Friend[count];
        for (int i = 0; i < count; i++) {
            input = br.readLine().split(" ");
            int price = Integer.parseInt(input[0]);
            int transportPrice = Integer.parseInt(input[1]);

            Friend friend = new Friend(price, transportPrice);
            friends[i] = friend;
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count; i++) {
            int[] totalArray = new int[count];
            for (int j = 0; j < totalArray.length; j++) {
                if (i == j) {
                    totalArray[j] = (friends[j].price / 2) + friends[j].transportPrice;
                } else {
                    totalArray[j] = friends[j].price + friends[j].transportPrice;
                }
            }

            Arrays.sort(totalArray);
            long sum = 0;
            int success = 0;
            for (int j = 0; j < totalArray.length; j++) {

                sum += totalArray[j];
                if (sum > money) {
                    break;
                } else {
                    success++;
                }
            }
            max = Math.max(max, success);
        }

        bw.write(max + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Friend {
    int price;
    int transportPrice;

    public Friend(int price, int transportPrice) {
        this.price = price;
        this.transportPrice = transportPrice;
    }
}

 

매 반복마다 반값 할인을 받는 선물을 다르게 적용해가며 기본 자금 B 안에서 선물을 얼마나 살 수 있는지 산출해냈고, 그 중에서 가장 많은 선물을 사는 경우를 구했다.

반값 할인을 받는 선물이 제 각각 달라지는 상황에 맞게끔 가지고 있는 자금 내부에서 구매할 수 있는 최적의 선물 갯수를 구하며, 그 중 가장 큰 값을 찾았으므로 그리디 알고리즘, 그리고 모든 선물들에 대해 한 번씩 반값 할인을 적용하여 선물을 얼마나 살 수 있는지 알아냈으므로 브루트포스 알고리즘에 해당된다.