백준 19621번: 회의실 배정 2

문제 설명

• 회의 시작시간, 회의 종료시간, 회의 참여인원이 주어집니다.
  회의는 중단될 수 없으면 회의실은 하나 입니다. 이때 적절히 회의를 진행해 최대 참여 인원을 구해야 합니다.
• https://www.acmicpc.net/problem/19621

접근법

• 제한조건에 회의 K는 K-1과 K+1과만 시간이 겹치며 다른 회의와는 시간이 겹치지 않는다고 했습니다. 이는 다른 K회의를 선택하면 K-1회의와 K+1회의는 선택할 수 없고, 그 외 회의는 K회의를 선택하는 거에 영향을 안받는다는 의미입니다.
  • 이는 연속된 두 값을 선택할 수 없는 상태로 최대값을 만드는 것과 동일합니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[Math.max(2, N)];
		int[] dp = new int[Math.max(2, N)];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			arr[i] = m;
		}
		dp[0] = arr[0];
		dp[1] = Math.max(arr[0], arr[1]);
		for (int i = 2; i < dp.length; i++) {
			dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]);
		}
		System.out.println(dp[N-1]);
	}
	
}