아직 계정이 없으신가요? 회원가입

관심 Tag

Talk 등록

Dev. Talk

[21년 재직자 대회 예선] 마이크로서버

회원사진7109417
268 views2021-11-09 12:42

문제 풀이 접근법을 다음과 같이 하였습니다

- 각 서버에 최대 어플리케이션 숫자는 3개이고, 이때는 전부 300MiB 이어야함

- 601MiB ~ 900MiB 부터는 서버에 1개 밖에 못넣으므로, 메모리를 숫자로 읽어서 parsing 할때 바로 counting 해줌

- list_weights 를 memory 가 300MiB ~ 600MiB 인 어플리케이션으로 채워둠 (이 안에 있는 어필리케이션은 1개 혹은 2개가 짝을 지어서 하나의 서버에 들어갈수 있음)

- list_weights 를 sorting 하고 큰 것부터 차례대로 서버에 할당하면서 같이 서버에 넣을수있는 어필리케이션 중 가장 큰 메모리를 가지고 있는 어플리케이션을 서버에 같이 넣음

- 효율을 위해 Counter 와 set 을 사용


이렇게 풀면 subtask 3,4 에서 일부 오답이 나오네요.. 혹시 도움 주실수 있는 분이 계실까요?



import sys

import bisect
from collections import Counter

T = int(sys.stdin.readline().rstrip())

def update( counter, sorted_list, val):
counter.subtract(Counter({val: 1}))
if counter[val] == 0:
del counter[val]
if val not in counter:
sorted_list.remove(val)
for _ in range(T):
_ = int(sys.stdin.readline().rstrip())
list_weights = []
count = 0
n_300 = 0
for el in [ int(el) for el in sys.stdin.readline().split()]:
if el == 300:
n_300 += 1
elif el > 600:
count += 1
else:
list_weights.append( int(el))
count += n_300// 3

list_weights += [ 300]*(n_300 % 3)
counter = Counter(list_weights)
unique_weight_sorted = sorted( set(counter.elements()))
while len(unique_weight_sorted)!= 0:
count+= 1
curr_w = unique_weight_sorted[- 1]
update(counter, unique_weight_sorted, curr_w)
cand_recip_w = 900 - curr_w
index_recip = bisect.bisect_right(unique_weight_sorted, cand_recip_w) - 1
if index_recip >= 0:
recip_w = unique_weight_sorted[index_recip]
update(counter, unique_weight_sorted, recip_w)

print(count)