글 읽기 - 반례를 못찾겠습니다 ㅠㅠㅠ 제발 도움 부탁드립니다ㅠㅠ

chuncccc1004 2년 전 0

반례가 뭐가 있을까요..?

# 가방이 허락하는 무게에 최대한의 가격의 보석을 넣어야 함
import sys
import heapq

N, K = map(int,sys.stdin.readline().rstrip().split())
zem_list = []
bag_list = []
price_sum = 0

for _ in range(N) :
    zem_list.append(list(map(int,sys.stdin.readline().rstrip().split()))) # 보석 정보 리스트에 저장 0 : 무게 / 1 : 가격
zem_list.sort(key=lambda x:x[1], reverse=True) # 가격 높은 순으로 정렬

for _ in range(K) :
    heapq.heappush(bag_list,int(sys.stdin.readline().rstrip()))

while bag_list :
    bag = heapq.heappop(bag_list)
    idx = 0
    for M, V in zem_list:
        if M <= bag:  # 가방 안에 들어갈 수 있는 무게
            price_sum += V
            zem_list = zem_list[idx+1:]
            break
        idx += 1

print(price_sum)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다 ㅠㅠㅠ 제발 도움 부탁드립니다ㅠㅠ

chuncccc1004 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말