글 읽기 - 최대 가치를 가지는 작업들을 수행하는 알고리즘, 반례나 조언 부탁드립니다.

(追記) (追記ここまで)

최대 가치를 가지는 작업들을 수행하는 알고리즘, 반례나 조언 부탁드립니다.

13904번 - 과제

choyj1127 2년 전 0

1. 과제 점수 기준 내림차순 정렬

2. 가장 과제 점수가 높은 것의 마감 기한 일자만큼 데이터들은 순차적으로 따로 리스트에서 빼냄

- 가장 과제 점수가 높은 것은 무조건 얻도록 하기 위함

3. 기한 기준 오름차순, 점수 기준 내림차순 정렬

4. 가능한 작업들 수행

5. 2에서 빼내고 남은 리스트를 기한 기준 오름차순, 점수 기준 내림차순 정렬한 후, 가능한 작업들을 수행

예제하고 이것저것 테스트 돌려봤는데 어떤 점에서 잘못된 건지 잘 모르겠습니다.. 후 도와주세요

import sys
input = sys.stdin.readline
day = 1
answer = 0
n = int(input())
works = [list(map(int, input().split())) for _ in range(n)]
works.sort(key=lambda x: -x[1]) # 과제 점수 기준 내림차순
a = works[0][0] # 가장 과제 점수가 높은 과제의 마감일
if len(works) >= a: # a개만큼 따로 빼내기
 arr = works[:a]
 works = works[a:]
else:
 arr = works[:]
 works = []
arr.sort(key=lambda x: (x[0], -x[1])) # 마감 기한 기준 오름차순, 과제 점수 기준 내림차순
for d, w in arr:
 if day <= d: # 점수 얻기
 answer += w
 day += 1
works.sort(key=lambda x: (x[0], -x[1])) # 마감 기한 기준 오름차순, 과제 점수 기준 내림차순
for d, w in works:
 if day <= d: # 점수 얻기
 answer += w
 day += 1
print(answer)

onegi95 2년 전 2

반례 드립니다.

7
4 100
2 10
1 20
2 50
5 99
5 99
5 99

output : 397

answer : 447

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC