[5911] 선물

2023-02-23 | Algorithms / 백준 문제 풀이 모음 # Python, Sliver 3

백준 문제 풀이

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)