[백준, Java] 19621번 : 회의실 배정 2

🔗 문제 링크

https://www.acmicpc.net/problem/19621

😮 문제 해결 방법

문제의 제한 조건에서 K 번째 회의는 K-1 , K+1번째 회의와 겹친다고 했기 때문에 K 기준으로 회의를 참석하는 경우 K-1, K+1회의는 참석할 수 없다.

반대로 회의에 참가하지 않는 경우 K-1, K+1 회의는 참가할 수 있다.

따라서, 첫 회의를 기준으로 참가하는 경우와 불참하는 경우로 DFS를 이용한 완전탐색으로 문제를 해결했다.

1. 회의의 최대 개수가25개까지 주어지므로 DFS를 이용한 완전탐색이 가능하다.
2. 첫 번째 회의 기준으로 참가와 불참 경우로 탐색을 진행한다.
   1. 첫 번째 회의에 참가하는 경우 2번째 회의는 참가하지 못하기 때문에 3번째 회의에 참가하도록 depth + 2를 해주고 현재 회의에 참여했으므로 현재까지의 회의 참가 인원 + 현재 회의 참가 인원을 넣어준다.
   2. 첫 번째 회의에 불참하는 경우 2번째 회의는 참가할 수 있기 때문에 2번째 회의에 참가하도록 depth + 1를 해주고 현재 회의에 불참했으므로 그대로 현재까지의 회의 참가 인원을 넣어준다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_19621_회의실_배정_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<Room> roomList = new ArrayList<>();
        for(int loop = 0; loop < N ; loop++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int headcount = Integer.parseInt(st.nextToken());
            roomList.add(new Room(start, end, headcount));
        }

        int rst = getMaxHeadcount(N, roomList);
        System.out.println(rst);

        br.close();
    }

    private static int headcount;
    private static int getMaxHeadcount(int n, List<Room> roomList) {
        headcount = 0;

        // n이 최대 25이므로 dfs를 이용한 완전 탐색 가능
        dfs(0, roomList, 0, n);

        return headcount;
    }

    private static void dfs(int depth, List<Room> roomList, int count, int n) {
        // List의 Max 인덱스가 n-1까지 이므로 이 이상이 되는 경우 모든 회의가 끝난 경우
        if(depth > n-1) {
            headcount = Math.max(headcount, count);
            return;
        }

        // 현재 회의 참여하는 경우 다음 회의 참여 못함
        dfs(depth + 2, roomList, count + roomList.get(depth).getHeadcount(), n);

        // 현재 회의 참여하지 않는 경우 다음 회의 참여
        dfs(depth + 1, roomList, count, n);
    }

    static class Room {
        private int start;
        private int end;
        private int headcount;

        public Room(int start, int end, int headcount) {
            this.start = start;
            this.end = end;
            this.headcount = headcount;
        }

        public int getStart() {
            return start;
        }

        public int getEnd() {
            return end;
        }

        public int getHeadcount() {
            return headcount;
        }
    }
}