개발자 톡
연습문제 톡
[21년 재직자 대회 예선] 마이크로서버
[21년 재직자 대회 예선] 마이크로서버
- 등록일
- 2021-11-09 12:42:32
- 조회수
- 878
- 작성자
- 7109417
문제 풀이 접근법을 다음과 같이 하였습니다
- 각 서버에 최대 어플리케이션 숫자는 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)
#[21년_재직자_대회_예선]_마이크로서버
#python