BOJ 25947 - 선물할인 (Python3)

수요가 많은 글이 어려운 문제의 해설이 아니라 적당한 난이도의 문제 해설이라는 것을 알고 최근 글을 둘러보았다. 문제 해설 글이 점점 줄어지기도 했거니와 내가 어렵게 풀어서 임팩트가 강하게 남은 문제들만 해설을 남기는 것 같은 기분이다.

분명 처음 블로그를 개설했을 때는 전혀 안 이랬는데... 실력이 는다고 자만했나? 그래서 과거 푼 문제를 뒤져보다가 굉장히 교육적이고 추천할 만한 문제를 발견해서 그 문제의 해설을 작성하려고 한다. 지난 해 ICPC 인터넷 예선의 예비소집 문제이기도 하고, 재작년 ICPC 인터넷 예선 문제이기도 하다. 퀄리티는 보장이 되어 있다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

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

 

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 \(n\) \((1\le n\le 100\,000)\), 예산을 나타내는 양의 정수 \(b\) \(1\le b\le 10^9)\), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 \(a\) \((0\le a\le n)\)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 \(n\)개의 선물 가격이 공백을 사이에 두고 주어진다. 선물 가격은 2 이상 10억 이하의 값을 갖으며, 항상 짝수로 주어진다.

 

예제 입력)

# 예제 입력 1
6 26 2
4 6 2 10 8 12

# 예제 입력 2
6 23 1
4 6 2 12 8 14

 

출력

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

 

예제 출력)

# 예제 출력 1
5

# 예제 출력 2
4

 

---

내 코드

N,B,A = map(int,input().split())
l = sorted(list(map(int,input().split())))
ans = 0
for i in range(A):
    ans += l[i]//2
    if ans > B: print(i); quit()
for i in range(A,N):
    ans += (l[i] + l[i-A])//2
    if ans > B: print(i); quit()
print(N)

 

중요한 관찰이 두 개가 필요하다. 하나는 똑같은 양의 선물을 사기 위해서는 싼 것부터 사는 게 이득이란 것. 다른 하나는 똑같은 선물들을 살 거라면 반값 할인은 비싼 것부터 적용시키는 게 이득이란 것. 돈을 최대한 아껴서 하나라도 선물을 더 사려면 최대한 돈을 남겨먹어야 하기 때문이다.

우선 싼 순서대로 \(a\)개의 선물을 하나씩 사 보면서 예산을 초과하는지 체크한다. 이 시점에서 얘산이 초과된다면 그냥 그대로 끝. 그렇지 않다면 이제는 싼 순서대로 \(i\)번째 물건까지 사 보자. 이 때, 살 선물에 \(i\)번째 선물이 추가되면 \(i-a\)번째 선물은 반값할인을 취소하고 그 대신 \(i\)번째 선물에 반값할인을 적용해 줘야 앞에서 말했던 중요한 관찰을 유지할 수 있다. 싼 것부터 사고 할인은 비싼 것부터.

이 과정에서 추가되는 돈은, 싼 순서대로 \(i\)번째 선물의 가격이 \(P_i\)라면 \(\frac12 (P_{i-a}+P_i)\)이다. 하나하나씩 계산하면 싼 순서대로 정렬하는 데 \(\mathcal O(N\log N)\)만큼 시간을 소모하고, 계산애 걸리는 시간은 \(\mathcal O(N)\)이므로 제한시간 안에 충분히 들어온다.

 

이로서 25947번의 풀이를 마친다.