[자바] 백준 19622 - 회의실 배정 3 (boj java)

문제 : boj19622

 

  문제 읽으면서 와.. 이거 N이 25 이하 정도가 아니라면 힘들꺼같은데 이걸 어떻게 하지 생각하면서 읽어내려오니 역시나 '임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.' 이런 조건이 있었다.

 

  그럼 그냥 dp로 쉽게 해결 가능하다. 결국 자신의 이전과 이후와 겹칠 수 없으므로, 방향을 입력이 주어지는 순서로 제한해보자면 결국 현재 회의를 개최하지 않는다면 이전 회의가 개최했던, 안했던 상관이 없다. 그리고 현재 회의를 개최하려면 이전 회의가 개최되지 않았어야 한다. dp 배열을 다음과 같이 정의하자.

 

  dp[i][0] -> i번째 회의를 개최하지 않을 경우 i번 회의까지의 최대 인원

  dp[i][1] -> i번째 회의를 개최할 경우 i번 회의까지의 최대 인원 (그리고 i번째 회의의 인원을 cur 이라 하겠다)

 

그럼 점화식은 다음과 같다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+2][2];
        for (int i = 2; i <= n+1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            st.nextToken(); st.nextToken();
            int cur = Integer.parseInt(st.nextToken());
            arr[i][0] = Math.max(arr[i-1][0], arr[i-1][1]);
            arr[i][1] = Math.max(arr[i-1][0], arr[i-2][1]) + cur;
        }
        System.out.print(Math.max(arr[n+1][0], arr[n+1][1]));
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}