백준 #32945 극한집업 - 영양사 선생님

문제 링크

[32945 극한집업 - 영양사 선생님]

문제 설명

학생들의 밥먹는 시간이 주어졌을 때 가장 많은 학생들이 밥먹고 있을 때의 학생 수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
time = [1] * (N + 2)
time[0] = 0
time[-1] = 0
for i in range(N):
    time[min(N + 1, arr[i] + i + 1)] -= 1
for i in range(1, N + 1):
    time[i] += time[i - 1]
print(max(time))

풀이

먼저 학생들이 각 시간대에 한명씩 밥을 먹는다 가정하고 time 리스트에 1씩 넣어놓는다. 밥먹는 시간을 역으로 정렬해준다! 역으로 정렬해준 이유는 밥을 길게 먹는 사람을 앞쪽에 배치함으로써 밥먹는 시간대를 최대한 많이 겹치게 하기 위함이다. 학생들 한명씩 돌아가면서 학생들이 식당을 떠나는 시간과 $N$중에서 작은 값을 time에서 하나씩 빼준다. time에서 앞에서부터 누적합을 해준다음 max값을 구해주면 끝!