[백준 25947번] 선물할인 (C++)

문제링크 : https://www.acmicpc.net/problem/25947

25947번: 선물할인

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N, B, A;
    cin >> N >> B >> A;
    int sum = 0;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr+N);

    int i, j=0;
    for(i=0; i<N; i++)
    {
        sum += arr[i]/2; //반값 더하기
        if(i+1 > A) sum+= arr[j++]/2; //뒤에 값이 반값이므로 앞에값 다시 더해주기 (반값 갯수 유지)
        if(sum > B) break;
    }

    cout << (sum > B ? i:N);

    return 0;
}

그리디 문제다. 

처음에 삽질을 좀 하고.. 다른 사람의 풀이를 참고하여 깔끔한 코드를 이해할 수 있었다.

 

정렬을 한 다음에 앞에서 부터 반값을 더해나가다가 반값의 갯수가 정해진 갯수를 넘어서면 앞의 저렴한 값의 반값을 취소하고 뒤에 더 비싼 값을 반값으로 만들어서 반값의 총 갯수를 유지한다.

 

ex : 반값 2개

반값 반값 원가 원가 > 반값 반값 반값 원가 -> 원가 반값 반값 원가

이런식으로 총 가격을 더해가다가 정해진 총 가격을 넘어서면 종료한다.

정해진 총 가격을 넘어서면 위 반복문의 i 값 (현재 카운트된 수)를 출력하고 아니라면 최대 값인 N을 출력한다.