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

---

분명 실버2인데 생각보다 까다로웠던 것 같다. ICPC 2022 인터넷 예선 당시에는 1초라는 압박감에 pq를 사용해야하나 고민하다 뒤늦게 반례를 찾아서 생각해낸 방법은 Greedy(탐욕법)이었다. 작은 것부터 챙겨나가다가 못챙기는 순간이 생기면 그 물건을 할인해서 넣을 수 있는지 확인하고 그 이후 가지고 있는 값 중에 가장 큰 값을 차례대로 줄여가며 구매할 수 있는지 체크하면 되는 간단한 알고리즘이었는데

긴장해서 그런지 구현이 생각보다 막혔던 것으로 기억한다.

 

백준에 제출할 때는 로직은 분명 맞는데 왜 틀리지하고 고민하다가 마지막에 + 1을 해주게 되어 처음부터 넣을 수 없는 아이템일 때도 1로 체크되는 문제가 있었다. 역시 10% 이내나 90%이내에서 터지면 경계값 확인을 하는게 제일 좋은 것 같다. 이외에 혹시 int로 터질 수 있겠다 싶어서 long long int를 사용하였는데 이 것 때문에 문제가 생기진 않을 것 같다. (9999999... + 1억 이면 int 범위 이내이다.)

흐르는대로 짜서 코드가 더럽긴 하다.

---

#include <bits/stdc++.h>
using namespace std ;
int item, buget, discount ;
long long int sum ;
int flag, answer ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> item >> buget >> discount ;
    vector<int> gift(item), ds_idx(item) ;

    for(int &it : gift)
        cin >> it ;

    sort(gift.begin(), gift.end()) ;
    
    for(int i = 0 ; i < item ; i++)
    {
        if(sum + gift[i] <= buget)
        {
            sum += gift[i] ;
            answer = i + 1;
        }
        else
        {
            flag = 0 ;
            for(int j = i ; j >= 0 ; j--)
            {
                if(ds_idx[j]) continue ;
                if(discount == 0) break ;
                sum -= gift[j] / 2 ;
                discount-- ;
                ds_idx[j] = 1 ;
                if(sum + gift[i] <= buget)
                {
                    flag = 1 ;
                    sum += gift[i] ;
                    answer = i + 1;
                    break ;
                }
            }
            if(!flag) break ;
        }
    }
    cout << answer ; 
}

---

느낀점: 방학 때 실랜디라도 해야겠다... 뭔가 실버 상위권은 골드45랑 비슷한데 알고리즘 모르고 보면 막히는 부분이나 내 약점을 찾을 수 있을 것 같다.

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

25947번: 선물할인