[5911] 선물

5911번: 선물

선물을 많이 주는 방법으로 금액을 나누어야 한다… 할인은 한명만 가능하고, 배송비는 별도로 할인이 안된다.

즉, 친구들 중 가격이 낮은(물건+배송비)순으로 배송을 보내는 것이 가장 이상적이다.

가격이 낮은 순으로 정렬하고, 한명씩 할인된 가격과 비교해서 많이 보낼 수 있는 값을 찾는다.

입력

각각 친구들의 물건값, 배송비를 입력받는다.

N, B = map(int, input().split())
    gifts = []
    for i in range(N):
        item = list(map(int, input().split()))
        gifts.append(item)

물건 값과 배송비 순으로 오름차순으로 정렬한다.

gifts.sort(key=lambda x: (x[0], x[1]))

정렬된 데이터에서 i 번째가 할인했을 때 총비용을 costs에 저장하고, 다시 정렬한다.

그러면, 각각 친구들에게 배송비를 포함해서 정렬되고, 비용이 costs에 저장되어있으니 이제 부터 합해서 보낸 횟수를 증가 시킨다.

내 돈을 넘으면 멈추고, 아니라면 최대 횟수와 비교해서 값을 저장한다.

max = 0
# print(gifts)
for i in range(N):
    costs = []
    for j in range(N):
        cost = 0
        if i == j:
            cost = (gifts[j][0]/2) + gifts[j][1]
        else:
            cost = gifts[j][0] + gifts[j][1]
        costs.append(cost)
    costs.sort()
    sum = 0
    p_count = 0
    for h in range(N):
        sum += costs[h]
        p_count += 1
        if sum > B:
            break
        else:
            if max < p_count:
                max = p_count

이 일련의 과정을 모두 거치면 max에는 보낸 횟수의 최대값이 들어감으로 출력한다.

풀이

if __name__ == '__main__':
    N, B = map(int, input().split())
    gifts = []
    for i in range(N):
        item = list(map(int, input().split()))
        gifts.append(item)

    gifts.sort(key=lambda x: (x[0], x[1]))
    max = 0
    # print(gifts)
    for i in range(N):
        costs = []
        for j in range(N):
            cost = 0
            if i == j:
                cost = (gifts[j][0]/2) + gifts[j][1]
            else:
                cost = gifts[j][0] + gifts[j][1]
            costs.append(cost)
        costs.sort()
        sum = 0
        p_count = 0
        for h in range(N):
            sum += costs[h]
            p_count += 1
            if sum > B:
                break
            else:
                if max < p_count:
                    max = p_count

    print(max)