[Algorithm] 2023 현대모비스 알고리즘 경진대회 예선 - 상담원 인원

import java.util.*;
class Solution {
    static int[] arr;
    static int[] ends;
    static int[][] req;
    static int answer = Integer.MAX_VALUE;
    
    public int solution(int k, int n, int[][] reqs) {
        // 12:40
        // 각 유형별로 멘토 적어도 한명 이상
        // 시각 오름차순, 겹치지 않음
        req = new int[reqs.length][3];
        
        for(int i = 0; i < reqs.length; i++) {
            req[i] = reqs[i].clone();
        }
        
        arr = new int[k];
        Arrays.fill(arr, 1);
        dfs(0, k, k ,n);
        return answer;
    }
    
    public void print(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public void dfs(int idx, int count, int k, int n) {
        if(count == n) {
            print(arr);
            int sum = 0;
            PriorityQueue<Integer>[] q = new PriorityQueue[k];
            for(int i = 0; i < k; i++) {
                q[i] = new PriorityQueue<>();
            }
            
            for(int[] r: req) {
                int start = r[0];
                int end = r[1] + r[0];
                int type = r[2]-1;
                
                if(q[type].size() < arr[type]) {
                    q[type].add(end);
                } else {
                    // 이미 끝나 있는게 있는 경우
                    int polled = q[type].poll();
                    if(polled <= start) {
                        q[type].add(end);
                    }
                        
                    // 이미 끝난게 없는 경우
                    else {
                        q[type].add(polled - start + end);
                        sum += polled - start;
                    }
                }
            }
            // System.out.println(sum);
            answer = Math.min(answer, sum);
            return;
        }
        
        for(int i = idx; i < k; i++) {
            arr[i] += 1;
            dfs(i, count+1, k, n);
            arr[i] -= 1;
        }   
    }
}

❗시간 초과가 났던 이유 - dfs 

수정 전

    public void dfs(int count, int k, int n) {
        if(count == n) {
            return;
        }
        
        for(int i = 0; i < k; i++) {
            arr[i] += 1;
            dfs(i, count+1, k, n);
            arr[i] -= 1;
        }   
    }
}

수정 후

    public void dfs(int idx, int count, int k, int n) {
        if(count == n) {
            return;
        }
        
        for(int i = idx; i < k; i++) {
            arr[i] += 1;
            dfs(i, count+1, k, n);
            arr[i] -= 1;
        }   
    }

조합 문제 안에서의 for 문은 0 부터 시작할 필요가 없다!