Softeer 금고털이 (난이도2)

정답 코드 1 (시간복잡도 O(NlgN) )

import sys
W, N = map(int, sys.stdin.readline().split())
backpack = []
for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    backpack.append([b, a, a * b])

backpack.sort(reverse=True, key=lambda x:x[0])

ans, point, total = 0, 0, 0
for i in range(N):
    total += backpack[i][1]
    ans += backpack[i][2]
    if total >= W:
        ans -= backpack[i][2]
        ans += backpack[i][0] * (W - total + backpack[i][1])
        break

print(ans)

정답 코드 2 (시간 복잡도 O(N) )

import sys
W, N = map(int, sys.stdin.readline().split())
j = [0 for i in range(10001)]
for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    j[b] += a


ans, total = 0, 0,
for i in range(10000, 0, -1):
    total += j[i]
    if total < W:
        ans += i * j[i]
    else:
        ans += i * (W - total + j[i])
        break

print(ans)

비슷한 문제

(백준 12865 평범한 배낭, DP)

N, K = map(int, input().split())

items = []
dp = [0 for i in range(100001)]

for i in range(N):
    a, b = map(int, input().split())
    items.append([a, b])

for i in range(N):
    for j in range(K, items[i][0] - 1, -1):
        dp[j] = max(dp[j],  dp[j - items[i][0]] + items[i][1])

print(dp[K])

알고리즘 유형

Greedy

배운 점

다 풀고 보니 시간복잡도가 nlogn이 아닌 n만큼 걸리게 풀 수 있었다.