[파이썬] 소프티어 금고털이

문제 확인

Softeer

• 사이트를 방문하여 문제를 확인해주세요.

나의 풀이

• 정렬엔 O(N)인 Count 정렬
• 최대 무게를 얻기 위한 idx를 찾기 위해선 O(logN)인 이진 탐색 사용
• idx를 찾는 경우엔 범위가 10,000이었기 때문에 단순 탐색으로도 시간 초과가 발생하지는 않았을 것이다.

귀금속의 종류(N)이 1,000,000이므로 $O(Nlog(N))$인 파이썬의 기본 정렬 대신 $O(N)$인 Counting 정렬을 사용했다.

이때, N(귀금속 종류의 수)가 P(귀금속 무게당 가치)보다 크기 때문에 P가 같은 경우가 발생할 수 있다.

P가 같은 경우엔 동일 P를 가지는 귀금속 과 구분할 수 없기 때문에 무게를 추가해줬다.

 

이후 최대 무게를 얻기 위한 idx를 찾기 위해 이진 탐색을 진행했다.

import sys

def binary_search(target):
    # index를 찾자
    start = 0
    end = j_class - 1
    while start <= end:
        mid = (start + end) // 2
        count = sum(w_list[:mid + 1]) # idx 찾기 위해서 mid + 1
        if count <= target:
            start = mid + 1
        elif count > target:
            end = mid - 1
    return mid

bag, j_class = map(int, input().split())
# 무게당 가격으로 정렬
# counting sort 사용
counting = [0] * (10**4 + 1)
for _ in range(j_class):
    w, p = map(int, input().split())
    if counting[p] == 0:
        counting[p] = [w, p]
    # 동일 무게 존재
    else:
        counting[p][0] = counting[p][0] + w
j_info = []
# 무게 당 가치가 큰 순으로 정렬
for i in range(10 ** 4, 0, -1):
    if counting[i] == 0:
        continue
    j_info.append(counting[i])
w_list, val_list = zip(*j_info)
# binary search로 idx 얻기
idx = binary_search(bag)
# 무게 계산
weight = sum(w_list[:idx])
val = sum([w_list[i] * val_list[i] for i in range(idx)])
# 가방 무게 확인
bag -= weight
val += bag * val_list[idx]
print(val)