[Beakjoon] 백준 5911번 Python

Beakjoon 5911, 선물
solved.ac Silver3
Greedy 알고리즘

문제

시흠이는 군대에 가기 전까지 자신과 놀아준 친구 N(1 ≤ N ≤ 1000)명에게 선물을 주려고 한다. 시흠이는 돈을 B(1 ≤ B ≤ 1,000,000,000)원 가지고 있다.

i번째 친구가 받고 싶어하는 선물의 가격은 P(i)원이고, 배송비는 S(i)원이다. 즉, 시흠이가 i번째 친구에게 선물을 보내려면 돈이 P(i)+S(i)원 필요하다.

시흠이는 물건 가격을 절반으로 할인받을 수 있는 쿠폰을 하나 가지고 있다. 이 쿠폰을 i번째 친구에게 사용한다면, ⌊P(i)/2⌋+S(i)원만 있으면 선물을 보낼 수 있다.

시흠이가 선물을 최대 몇 명에게 보낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 B가 주어진다. 둘째 줄부터 N개 줄에는 P(i)와 S(i)가 주어진다. (0 ≤ P(i), S(i) ≤ 1,000,000,000)

출력

첫째 줄에 시흠이가 선물을 최대 몇 명에게 보낼 수 있는지 출력한다.

Solution

n, m = map(int, input().split())

p = []
s = []
result = []
for i in range(n):
    pi,si = map(int, input().split())
    p.append(pi)
    s.append(si)

for i in range(n):
    data = []
    for j in range(n):
        if i == j:
            data.append(p[j] // 2 + s[j])
        else:
            data.append(p[j] + s[j])
    count = 0
    sum = 0
    data.sort()
    for j in range(n):
        sum += data[j]
        if sum > m:
            break
        count += 1
    result.append(count)   

print(max(result))

풀이

입력받은 물건 값이랑 배송비를 합한 리스트를 만들어 줄 겁니다. 이때 물건 1개는 반값으로 해서 리스트를 만들어줍니다.

2중 반복문으로 물건값 + 배송비 리스트가 만들어 질때마다 최대로 보낼 수 있는 사람의 수를 count 리스트에 추가합니다.

그중에서 가장 큰 수를 출력합니다.

---

5911번: 선물