[DP][JAVA] 회의실 배정 2

🔗문제 링크 

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

19621번: 회의실 배정 2

문제

서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다.각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다.

단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작 시간은 끝나는 시간보다 항상 작다.

N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.

 

입력

첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 N + 1 줄까지 공백을 사이에 두고

회의의 시작시간, 끝나는 시간, 회의 인원이 주어진다.

 

출력

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

 

제한

• 1 ≤ N ≤ 25
• 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.

 

 

---

이 문제는 DP로 해결한다. 

 

DP는 "Dynamic Programming"의 약자로, 동적 계획법을 의미한다.

동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법

 

import java.io.*;
import java.util.*;

public class Main {

	//회의의 보상을 저장하는 schedule 배열
    static int[] schedule;
    //최대 보상을 저장하는 dp 배열
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //회의의 수 입력받음
        int N = Integer.parseInt(br.readLine());

        schedule = new int[N + 1];
        dp = new int[N + 1];

		//N개의 회의에 대한 정보를 입력받아 schedule 배열에 보상을 저장
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int reward = Integer.parseInt(st.nextToken());
            //schedule 배열에는 인원수 저장
            schedule[i] = reward;
        }

		//첫 번째 회의의 보상을 dp 배열의 첫 번째 값으로 설정
        dp[1] = schedule[1];

		//회의가 2개 이상인 경우에만 아래의 로직을 실행
        if (N >= 2) {
        	 //두 번째 회의의 보상을 dp 배열의 두 번째 값으로 설정합니다. 
             //첫 번째 회의와 두 번째 회의 중 보상이 큰 값을 선택합니다.
             //겹치기 때문에 둘 중 하나만 선택해야함
            dp[2] = Math.max(schedule[1], schedule[2]);
        }

		//세 번째 회의부터 마지막 회의까지 순회하면서 최대 보상을 계산
        for (int i = 3; i <= N; i++) {
        	//현재 회의를 선택하는 경우와 선택하지 않는 경우 중 
            //보상이 큰 값을 선택하여 dp 배열에 저장합니다. 
            
            //dp[i - 2]+ schedule[i]는 현재 회의의 보상과 
            //두 번째 전 회의까지의 최대 보상을 더한 값이고,
            //dp[i - 1]은 이전 회의까지의 최대 보상입니다.
            dp[i] = Math.max(dp[i - 2] + schedule[i], dp[i - 1]);
        }
        
		//마지막 회의까지의 최대 보상을 출력합니다.
        System.out.println(dp[N]);
    }
}

 

스케줄의 시작 시간, 종료 시간 및 보상을 배열에 저장하고 , DP 테이블을 구성하여 최대 보상을 계산합니다.

 

 

 

💡만약 회의가 2개라면 for문은 실행안되야 하는거 아니야 ?

:만약 회의가 2개라면 for 루프는 실행되지 않을 것입니다. for 루프는 i가 3부터 N까지 반복하므로,
N이 2라면 조건에 맞지 않아 for 루프의 내용이 실행되지 않습니다.
따라      서 for 루프는 회의가 3개 이상인 경우에만 실행됩니다.