백준 17305 - 사탕 배달

문제

사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si 를 계산해 놓았다. si 는 양의 정수로, si 가 클수록 사탕은 달콤하다.

shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만, 연약한 아기 석환은 가방에 최대 wg (w그램) 의 사탕만을 담을 수 있다. 아기 석환이 이 조건을 만족하면서 사탕을 담았을 때, 담아간 사탕의 당도의 합은 최대 얼마가 될 수 있을까?

백준 : https://www.acmicpc.net/problem/17305

해결

이 문제는 중량이 3g, 5g으로 인풋이 들어온다. 그리고 최대 당도를 섭취하는게 목표이므로 각 중량당 가장 높은 당도를 가진 사탕순으로 섭취해야한다. 그러므로 각 중량당 당도 순으로 정렬 후 누적합으로 계산하면 원하는 값을 얻을 수 있다.

arr3 = sorted(arr3, key=lambda x:-x[1])
arr5 = sorted(arr5, key=lambda x:-x[1])

pre_arr3 = [0]
for i in range(len(arr3)):
    pre_arr3.append(pre_arr3[i] + arr3[i][1])

pre_arr5 = [0]
for i in range(len(arr5)):
    pre_arr5.append(pre_arr5[i] + arr5[i][1])

주어진 중량에 대하여 먼저 3g만 전부 먹었을 때의 당도값을 구하고 이 3g 사탕을 한개씩 덜먹고 나머지를 5g 먹었을 때의 당도값 ~ 전부 5g을 먹었을 때의 당도값을 구했을 때 그 중 최대 당도값을 구하면 그것이 답이된다.

arr3_num = min(int(w/3), len(arr3))
max_val = 0
while arr3_num >= 0:
    arr5_num = min(int((w-arr3_num*3)/5), len(arr5))
    max_val = max(max_val, pre_arr3[arr3_num] + pre_arr5[arr5_num])
    arr3_num -= 1

github : https://github.com/teal94/ps/blob/master/bj/17305.py

1 글 1 고양이