99클럽 코테 스터디 18일차 TIL + Backtracking

문제

Programmers: 상담원 인원

• 설명: 멘토의 수, 상담 유형과 상담 요청 시간이 주어졌을 때 대기시간을 최소로 하도록 멘토들을 상담 유형에 배치하라

풀이

• 멘토들을 배치할 수 있는 모든 경우의 수를 따져보며 각 경우의 수마다 대기 시간을 구한다.
  • 최소 대기 시간이 답이다!
• 백트래킹으로 구현하였다.
• 또한 가장 빨리 끝나는 시간에 다음 상담 요청이 수락되어야하기 때문에 우선순위 큐로 멘토들의 스케쥴을 관리해주었다.
  • 사실 멘토가 최대 15명 밖에 안되서 매번 정렬한 다음에 0번째 값을 빼도 된다.
  • 물론 0번째 값을 빼는 건 $O(n)$이라 마음에 안든다면 내림차순 정렬한 다음에 맨 뒤의 값을 빼주자.

오늘의 회고

• 처음에 경우의 수 계산을 잘못해서 $5^{15}$로 계산했다. 그에 따라 아무생각 없이 그리디로 푸려다가 시간을 좀 많이 낭비했다.
• 생각한 경우의 수...
  

  

• 오늘따라 머리가 너무 안돌아가서 단순한 백트래킹 구현도 굉장히 많은 시간이 들었다..! 요즘 PS를 하면 할수록 실력이 퇴화되는 것 같은 느낌이 든다...
  • 지치지말고 화이팅 해보자

Code

# Programmers214288.py
from queue import PriorityQueue

# mentors: 각 유형별 멘토 수
def simulation(mentors, k, reqs):
    wait_time = 0
    pq = [PriorityQueue() for _ in range(k + 1)]

    for start, time, type in reqs:
        prev_end_time = 0
        # 해당 유형의 멘토가 남아있지 않는 경우
        if pq[type].qsize() >= mentors[type]:
            prev_end_time = pq[type].get()
            if prev_end_time > start:
                wait_time += prev_end_time - start
        pq[type].put(max(prev_end_time, start) + time)

    return wait_time


def solution(k, n, reqs):
    mentors = [1] * (k + 1)

    ans = 0x3f3f3f3f
    def solve(curr, idx):
        nonlocal ans
        if curr > n:
            return

        if curr == n:
            ans = min(ans, simulation(mentors, k, reqs))
            return

        if idx > k:
            return

        for i in range(n - k + 1):
            mentors[idx] += i
            solve(curr + i, idx + 1)
            mentors[idx] -= i

    solve(k, 1)

    return ans