백준 19621번 회의실 배정 (java)

[Silver II] 회의실 배정 2 - 19621

문제 링크

성능 요약

메모리: 14168 KB, 시간: 132 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 18일 20:28:19

문제 설명

서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.

입력

첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 N + 1 줄까지 공백을 사이에 두고 회의의 시작시간, 끝나는 시간, 회의 인원이 주어진다.

출력

첫째 줄에 회의실에서 회의를 진행할 수 있는 최대 인원을 출력한다.

풀이

dfs를 활용해서 완전탐색으로 풀이했다.

정렬을 하면 좀 더 빠르게 구현할 수 있을 거 같긴하나, N이 25밖에 되지 않아 완탐으로 풀이했다.

전체 코드

public class Main {
    static int N,x[][], max = 0;

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        x = new int[N][3];
        for(int  i = 0 ;i<N;i++){
            StringTokenizer st  = new StringTokenizer(br.readLine());

            x[i][0] = Integer.parseInt(st.nextToken());
            x[i][1] = Integer.parseInt(st.nextToken());
            x[i][2] = Integer.parseInt(st.nextToken());
        }

        dfs(0,0);

        bw.write(String.valueOf(max));
        bw.flush();
    }

    public static void dfs(int sum, int now){
        if(max < sum){
            max = sum;
        }

        for(int  i = 0 ;i<N;i++){
            if(now <= x[i][0]){
                dfs(sum + x[i][2], x[i][1]);
            }
        }
    }
}