[Baekjoon] 19622_회의실 배정 3

문제(출처: https://www.acmicpc.net/problem/19622)

---

< 회의실 배정 3 >

 

문제 풀이 

 

임의의 회의 k는 k-1과 k+1 회의와 시간이 겹치고 다른 회의들은 겹치지 않으므로(k-2 회의 + k 회의, k-1 회의) 중에 최댓값을 선택한다.

 

my solution (Java)

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

public class _19622_ { // 회의실 배정 3
	static class Info {
		int start;
		int end;
		int num;

		public Info(int start, int end, int num) {
			this.start = start;
			this.end = end;
			this.num = num;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		Info arr[] = new Info[n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i] = new Info(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));
		}

		int dp[] = new int[n];
		dp[0] = arr[0].num;

		if (n > 1) {
			dp[1] = Math.max(dp[0], arr[1].num);
		}

		for (int i = 2; i < n; i++) {
			dp[i] = Math.max(dp[i - 2] + arr[i].num, dp[i - 1]);
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			result = Math.max(result, dp[i]);
		}

		System.out.println(result);
	}
}

변수)
n : 회의의 수
arr : 회의 정보를 저장하는 배열
dp : 회의를 진행할 수 있는 최대 인원을 구하는 배열
result : 회의를 진행할 수 있는 최대 인원

 

회의의 수를 입력받는다. 회의의 수만큼 회의 정보를 입력받아 배열에 저장한다. dp의 0번째를 0번째 회의에 참석하는 인원으로, 1번째를 0번째와 1번째 회의에 참석하는 인원 중 최댓값으로 초기화한다. 나머지를 탐색하며 현재 회의를 선택한다면 dp[i-2]+현재 회의 참석 인원, 현재 회의를 선택하지 않는다면 dp[i-1] 이므로 둘 중에 최댓값으로 저장한다. 

 

최종 dp를 탐색하며 최댓값을 출력한다.

---

---