백준 25947 - 선물 할인 (자바 - 그리디)

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

25947번: 선물할인

 

* 문제 요약

n 개의 선물 가격이 주어졌을 때, b의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대 a개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오.

단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다.

 

* 입력

첫 번째 줄에 선물의 갯수를 나타내는 양의 정수 n(1 <= n <= 100,000), 예산을 나타내는 양의 정수 b (1 <= b <= 10^9), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 a (0 <= a <= n) 가 공백을 사이에 두고 차례로 주어진다.

다음 줄에 n개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 2이상 10억 이하의 값을 가지며, 항상 짝수로 주어진다.

 

* 출력

조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.

 

* 예시

 

* 해결 과정

각 선물의 가격을 배열에 받아서 오름차순으로 정렬해준 다음, 선물 구매 시작지점(start) 과 선물 구매종료 지점(end) 를 각각 0으로 초기화 해주고 아래와 같이 로직을 진행했다.

1. 할인 기회가 남아있는 경우

- 현재까지 총 사용한 금액(sum) + 선물 할인 금액(giftArray[i] / 2) 이 예산(money) 보다 작거나 같은 경우 현재까지 총 사용한 금액에 현재 탐색중인 선물을 반값 할인한 가격을 합산해주고, 반값 할인 기회를 1 줄인 다음 최대 선물 구매범위(end) 를 1 증가시킨다.

- 만약 현재까지 총 사용한 금액과 현재 탐색중인 선물을 반값 할인한 가격을 합산한 값이 예산을 초과하는 경우 반복문을 종료시킨다.

2. 할인 기회가 남아있지 않은 경우

- 기존에 반값 할인 받았던 선물들 중 가장 가격이 싼 선물(선물 구매 시작지점 - start) 에 대해 할인을 취소하고 (+ giftArray[start] / 2) 현재 탐색중인 선물 (선물 구매 종료지점 - end) 에 대해 할인을 적용해서 구매한 다음 ( + giftArray[end] / 2) 예산을 초과하는지 그렇지 않은 지 확인한다.

- 예산을 초과하지 않을 경우 start 와 end 를 각각 1씩 늘려서 다음 반복에서 할인을 취소할 선물, 새로 할인을 받아서 구매할 선물의 인덱스를 지정해둔다.

- 만약 예산을 초과할 경우 즉시 반복문을 종료한다.

 

반복문이 진행되는 동안 위의 로직을 거친 후, 반복문이 종료되고 나면 최종적으로 선물을 최대 몇 개(end) 구매 가능한지 출력시켜 준다.

 

* 코드

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]);
        long money = Long.parseLong(input[1]);
        int disCount = Integer.parseInt(input[2]);
        long sum = 0;

        input = br.readLine().split(" ");
        int[] giftArray = new int[count];
        for (int i = 0; i < count; i++) {
            giftArray[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(giftArray);
        int start = 0; 
        int end = 0; 
        for (int i = 0; i < giftArray.length; i++) {
            if (disCount > 0) {
                if (sum + (giftArray[i] / 2) <= money) {
                    sum += (giftArray[i] / 2);
                    disCount--;
                    end = i + 1;
                } else {
                    break;
                }

            } else {
                sum += (giftArray[start] / 2);
                sum += giftArray[end] / 2;

                if (sum > money) {
                    break;
                } else {
                    start++;
                    end++;
                }
            }
        }
        bw.write(end + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 할인 기회가 남아있는 경우, 그렇지 않은 경우에 따라 조건을 나눈 다음, 각 조건에 맞는 로직을 작성하고 수행해주었다.

선택된 해답이 조건을 만족하는지 검사한다. -> 반복문이 끝날때까지 최대 선물 구매가능 갯수를 특정할 수 없으므로 반복문을 지속한다. 

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘에 해당된다.