문제
- 멘토 N명은 1~k번의 상담 유형 중 하나만 담당한다.
- 멘토는 자신이 담당하는 유형의 상담만 가능하고, 동시에 참가자 한 명과 상담 가능하다.
- 참가자가 상담 요청
- 상담 유형이 일치하는 여유 멘토가 상담
- 없다면 기다림
- 멘토는 먼저 상담 요청한 순서대로 대기 참가자와 상담을 함
- 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원 정하기 (유형별로 멘토 인원이 적어도 한 명 이상)
- 1 <= k <= 5
k <= n <= 20
3 <= 상담 요청 개수 <= 300
풀이
- 다음 두 가지의 계산이 필요하다.
- 1) 각 상담 유형별 몇 명의 멘토가 배정되어야 하는지
- 2) 멘토가 배정되었을 때, 최소 대기 시간 구하기
- 2) 멘토 인원이 정해졌을 때, 최소 대기 시간 구하기
- 상담 요청을 요청 시각이 빠르고, 대기 시간이 적은 순서대로 정렬한 뒤 차례로 확인한다.
- 상담 유형별로 분리해 확인한다. (reqs_dic)
- waiting_time[i][j] : i 유형에 멘토가 j명일 때 최소 대기 시간
- 멘토 별로 다음 상담이 가능한 시각을 heap에 저장하고,
상담 요청이 들어올 때마다 가장 빠르게 상담이 끝나는 시각을 확인한다.
- 현재 시각에서 대기 없이 가능하다면, 다시 해당 멘토의 상담 끝나는 시각을 업데이트 하고
- 대기가 필요하다면 대기 시간을 더해주고, 해당 멘토의 상담 끝나는 시각을 업데이트 해준다.
- 1) 멘토 인원 조합
- bfs를 이용해 각 유형별로 1명씩 지정해준 뒤, 남은 인원을 모두 배정해준다.
모든 멘토가 배정된 뒤 각 유형별 대기 시간의 총합을 구해 최솟값을 찾는다.
- 또는 combinations 을 사용할 수 있다.
from collections import defaultdict
from collections import deque
import heapq
def solution(k, n, reqs):
reqs.sort() # 요청 시각이 빠르고, 대기 시간이 적은 순서대로 정렬
reqs_dic = defaultdict(list) # 상담 유형별로 분리
for a, b, t in reqs :
reqs_dic[t].append((a, b))
# 1. 멘토 인원별 대기 시간 구하기
# waiting_time[i][j] : i 유형에 멘토가 j명일 때 최소 대기 시간
waiting_time = [[0]*(n+1-k+1) for _ in range(k+1)]
for typ in range(1, k+1) :
# 1-1. 해당 유형에 요청한 상담이 없는 경우 pass
if reqs_dic[typ] == [] : continue
# 1-2. 해당 유형 별로 멘토 수에 따른 대기 시간 계산하기
for num in range(1, n+1-k+1) :
mentors = [0] * num # 멘토별 다음 상담 시간
for t_req, time in reqs_dic[i] :
# 가장 빠르게 상담이 끝나는 시각 확인
end_time = heapq.heappop(mentors)
# 상담 요청하기
if end_time <= t_req : # 바로 상담요청 가능
heapq.heappush(mentors, t_req + time)
else : # 대기 필요
waiting_time[i][j] += end_time - t_req
heapq.heappush(mentors, end_time + time)
# 2. 멘토 인원 조합
answer = 1e9
q = deque([ (n-k, [1] * (k+1)) ])
visited = set()
while q :
n, m = q.popleft() # 남은 멘토 수, 유형별 멘토 수 리스트
if n == 0 : # 모든 멘토가 배정된 경우
# 해당 경우의 수에 대한 최소 대기시간 구하기
total = 0
for i in range(1, k+1) :
total += waiting_time[i][m[i]]
answer = min(answer, total) # 정답 업데이트
continue
# 각 유형 별로 멘토 한 명씩 배정하기
for i in range(1, k+1) :
m[i] += 1
# 확인 해보지 않은 멘토 수 조합인 경우만 확인하기
if tuple(m) not in visited :
q.append((n-1, m[:]))
visited.add(tuple(m))
m[i] -= 1
return answer
References
- 프로그래머스 2023 현대모비스 알고리즘 경진대회 예선
