[백준/Python] #29155 개발자 지망생 구름이의 취업 뽀개기

문제

알고리즘

난이도 별로 정해진 개수만큼 문제를 골라서 전체 시간을 최소화하는 문제이다.

난이도를 증가시키는 경우 60분이 필요하므로 240분은 무조건 소요가 된다.

시간을 최소화하려면, 해당 난이도에서 최소 시간으로 문제를 고른뒤에 해당 문제를 오름차순 정렬해서 차이가 최소화 되도록 하면 된다.

먼저, 문제를 입력받고 해당 문제들을 난이도 별로 나눈다.

난이도마다 오름차순으로 정렬후에 선택해야 하는 문제수만큼 작은것부터 고른다. 그렇다면 해당 난이도에서 휴식시간을 계산하기 위해 오름차순정렬해서 반복문을 할 필요없이 선택된 문제중에 최대값과 최소값의 차이로 휴식시간을 계산해 주면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int, input().split()))

problems = [[] for _ in range(5)]

for _ in range(n):
    k, t = map(int, input().split())
    problems[k-1].append(t)

total_time = 0

for i in range(5):
    probs = sorted(problems[i])
    selected = probs[:p[i]]
    total_time += sum(selected)
    total_time += max(selected) - min(selected) if p[i] > 1 else 0

total_time += 60 * 4

print(total_time)