백준 사탕 배달(17305)

사탕 배달

1. 힌트

1) 흔한 배낭 문제처럼 보이지만 범위에서 볼 수 있듯이 DP로는 해결이 불가능합니다.

2) 만약 무게 $3$짜리 사탕을 $x$개 집는다면 당연히 남은 공간으로 무게 $5$짜리 사탕을 최대한 집는것이 이득입니다.

3) 가능한 $x$개에 대해 모두 확인해본다고 해도 $O(N)$에 해결 가능합니다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

우리가 찾고자 하는 최적해를 $(p,\ q)$로 나타낼 수 있는데 $p$와 $q$는 각각 $3,\ 5$짜리 사탕을 몇개 담는지를 나타냅니다.
그런데 $p$개를 집을거라면 당연히 $3$짜리 사탕에서 가장 당도가 높은 사탕 $p$개를 집는것이 이득입니다. $q$도 마찬가지입니다.
주어진 수열을 정렬하고 $3$짜리 사탕을 집을수 있는 경우의 수를 모두 시도하면 $5$짜리 사탕을 몇개 집을지는 자동으로 정해집니다. 따라서 $O(N)$으로 해결 가능합니다.

3. 구현

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
# 정렬할 때 맨 앞에 0이 있게 하도록 추가함
S3 = [1000000000]; S5 = [1000000000]
for i in range(N):
    t, s = map(int ,input().split())
    if t == 3 : S3.append(s)
    else : S5.append(s)
S3.sort(reverse = True); S5.sort(reverse = True);
S3[0] = S5[0] = 0
# 누적합 배열을 만든다 S3[i] = 3 사탕을 i개 골랐을 때 당도 합 
for i in range(1, len(S3)) : S3[i] += S3[i - 1]
for i in range(1, len(S5)) : S5[i] += S5[i - 1]
ret = 0
for i in range(min(len(S3) - 1, W // 3) + 1):
    ret = max(ret, S3[i] + S5[min(len(S5) - 1, (W - 3 * i) // 5)])
print(ret)

1) 시간 복잡도

$O(N)$

2) 테스트 케이스