25947번 (1) 썸네일형 리스트형 [백준/C++] 25947번 선물할인 분명 실버2인데 생각보다 까다로웠던 것 같다. ICPC 2022 인터넷 예선 당시에는 1초라는 압박감에 pq를 사용해야하나 고민하다 뒤늦게 반례를 찾아서 생각해낸 방법은 Greedy(탐욕법)이었다. 작은 것부터 챙겨나가다가 못챙기는 순간이 생기면 그 물건을 할인해서 넣을 수 있는지 확인하고 그 이후 가지고 있는 값 중에 가장 큰 값을 차례대로 줄여가며 구매할 수 있는지 체크하면 되는 간단한 알고리즘이었는데 긴장해서 그런지 구현이 생각보다 막혔던 것으로 기억한다. 백준에 제출할 때는 로직은 분명 맞는데 왜 틀리지하고 고민하다가 마지막에 + 1을 해주게 되어 처음부터 넣을 수 없는 아이템일 때도 1로 체크되는 문제가 있었다. 역시 10% 이내나 90%이내에서 터지면 경계값 확인을 하는게 제일 좋은 것 같다... 이전 1 다음