2023 현대모비스 예선 - 상담원 인원

• https://school.programmers.co.kr/learn/courses/30/lessons/214288
• 현대 모비스 경진대회 예선 문제가 떠서 그 중 1번 문제를 풀어보았다.
  • 2번은 20점 나옴... 디버깅(?)은 보류 중이다ㅠ

나의 풀이

• 문제 유형은 구현인 것 같다.
  • 브루트 포스와 정렬을 활용하는?
• 탑다운 디피? 를 이용해서 각 상담 유형의 멘토수 별 대기 시간을 2차원 배열에 저장했다.
  • 최소 힙😍을 이용해서 최단 대기시간 상담원을 바로 탐색할 수 있도록 했다.
• 브루트 포스 + dfs 를 이용해서 모든 케이스의 대기 시간 조합을 구현한다.
  
  • 기존 최소 시간을 초과해버리는 경우는 백트래킹하도록 한다.

# 상담 유형 k
# 멘토 수 n
# 요청
from collections import defaultdict
def solution(k, n, reqs):
    answer = 0
    cap = n - k  # 분배 가능 인력
    w_list = defaultdict(list)
    waiting = [[0] * (cap + 2) for _ in range(k+1)] # 멘토 수 별 웨이팅 타임

    def make_list():
        for (a, d, t) in reqs:
            w_list[t].append((a,d))    
        
    make_list()
    
    # 최대 20명이니 완탐? 혹은 그리디
    # 테이블에 최대 걸리는 시간을 저장하면서 완탐한 듯
    def check_waiting(t, n):
        import heapq  # 최소힙 사용하기
        mentors = [0]*n  # 멘토별 상담 졸료시간
        #heapq.heapify(mentors)
        
        for (a, d) in w_list[t]:  # (요청 시각, 상담 소요 시간)
            least = heapq.heappop(mentors)  # 최소 상담 시작 가능 시간
            diff = least - a  # 대기 시간
            start = a  # 시작 시간
            if diff > 0 :
                waiting[t][n] += diff
                start = least
            heapq.heappush(mentors, start+d)
            
    for i in range(1, k+1):
        for c in range(1, cap+2):
            check_waiting(i, c)
    
    min_v = float('inf')
    def dfs(depth, cap, curr):
        nonlocal min_v    
        if min_v < curr + waiting[k][1+cap]:
            return
            
        if depth == k:
            if min_v > curr + waiting[k][1+cap]:
                min_v = curr + waiting[k][1+cap]
            return
        
        for i in range(1, cap+2):
            dfs(depth+1, cap-i+1, curr+waiting[depth][i])
            
    dfs(1, cap, 0)
    
    return min_v

 

다른 사람 풀이

• 대충 봤는데, 각 경우에 따른 대기 시간을 따로 배열에 저장하지 않고 바로 구하는 로직이 많은 듯 했다.
  • 어떻게 구한 건지... 살펴 봐야 함......................ㅜ