[BOJ/Silver 1] 백준 25947 선물할인(C++)

문제 링크

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억 이하의 값을 갖으며, 항상 짝수로 주어진다.

 

출력

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

 

예제 입력 1

6 26 2
4 6 2 10 8 12

예제 출력 1

5

예제 입력 2

6 23 1
4 6 2 12 8 14

예제 출력 2

4

 

알고리즘 분류

• 그리디 알고리즘
• 누적 합

 

풀이

먼저 N개의 선물을 가격을 기준으로 오름차순 정렬한다.

그리고 첫 번째 선물부터 A개의 선물을 반값에 구매하며 가격을 누적시킨다.

만약 반값에 구매하는 도중에 예산을 넘어버리면 구매를 종료한다.

A개의 선물을 반값에 구매해도 예산이 넘지 않는다면 그 다음 선물을 반값에 구매하며 첫 번째 선물부터 원래 가격으로 다시 구매한다.

원래 가격으로 다시 구매할 선물의 절반의 가격만큼 예산을 추가로 누적하면 해당 선물은 원래 가격으로 구매한 것이 된다.

이렇게 마지막 선물까지의 가격을 확인하면 예산이 넘지 않는 선에서 구매할 수 있는 선물의 최대 개수를 구할 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, S;
LL B, M;
vector<LL> Presents;
int Answer = -1;

void input() {
    cin >> N >> B >> A;
    Presents.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> Presents[i];
    }
}

void settings() {
    sort(Presents.begin(), Presents.end());
    for (int i = 0; i < A; i++) {
        int Now = (Presents[i] / 2);
        if ((M + Now) <= B) {
            M += Now;
        }
        else {
            Answer = i;
            break;
        }
    }

    if (Answer == -1) {
        Answer = A;
        for (int i = A; i < N; i++) {
            int First = (Presents[S] / 2);
            int Now = (Presents[i] / 2);
            if ((M + First + Now) <= B) {
                M += (First + Now);
                Answer++;
                S++;
            }
            else {
                break;
            }
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}