[백준 19622] 회의실 배정3 (JAVA)

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

19622번: 회의실 배정 3

---

EASY~

 

문제는 단순하다

 

회의실이 1 개 있고,

 

n 개의 회의 정보가 주어진다.

 

회의 정보는 시작시간, 종료시간, 참석 인원으로 이루어져있다.

 

주어진 상황에서 가장 많은 인원이 회의를 참석할 수 있을 때,

 

그 인원의 수를 계산하면 된다.

 

회의 정보는 항상 시작 시간 < 종료 시간을 만족한 상태로 주어진다.

 

그리고 중요한 조건이 하나 있는데...

 

K 번째 회의는 K-1, K+1 번째 회의랑만 시간이 겹친다는 제약이다.

 

이 조건 덕분에 문제의 난이도가 확 떨어진다.

 

K 번째 회의를 택하면 K - 1 번째 회의는 택할 수 없다.

 

즉,

 

K-2 번째 회의를 택하고, K 번째 회의를 택하는 경우와

 

K-1 번째 회의를 택하고, K 번째 회의를 택하지 않는 경우 중

 

더 좋은 경우(인원 수가 더 많은 경우 ~> 이 경우에는 max 연산)를 갱신해나가면 된다.

 

즉,

 

f(x) 를 x 번째 회의까지 고려했을 때, 참석가능한 인원의 최대값이라고 정의하면

 

f(x) = Max (f(x-2) + people(x),  f(x-1)) 이라는 점화식을 완성할 수 있다.

 

( 여기서 people(x) 는 x 번째 회의에 참여하기로 예정된 인원 수를 의미한다. )

 

점화식을 쉽게 도출할 수 있으므로

 

bottom - up 방식으로 dp table 을 채워나갈 수 있다.

 

dp[0] 은 0 번째 회의의 참석 인원을 넣어주면 될 것이고,

 

dp[1] 은 dp[0] 과 people[1] 중 더 큰 값으로 초기화 하면 된다.

 

dp[2] 부터 n-1 까지는 위에서 도출한 점화식으로 채워나가면

 

최종 답안은 dp[n-1] 이 된다.

 

 

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine()); // 회의 수
        int[][] table = new int[n + 1][3];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            table[i][0] = Integer.parseInt(stk.nextToken());
            table[i][1] = Integer.parseInt(stk.nextToken());
            table[i][2] = Integer.parseInt(stk.nextToken());
        }

        long[] dp = new long[n + 1];

        dp[0] = table[0][2];
        dp[1] = Math.max(dp[0], table[1][2]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + table[i][2], dp[i - 1]);
        }
        bw.write(dp[n - 1] + "\n");

        bw.flush();
        bw.close();
    }
}

 

위 문제는 

 

" K 번째 회의는 K-1, K+1 번째 회의랑만 시간이 겹친다는 제약 " 덕분에 쉽게 풀 수 있었다.

 

이 조건이 없어진다면..??

 

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

19623번: 회의실 배정 4

그러면 위 문제 상황이 되는데,

 

이건 내일 풀어야겠다 ^_^