[Baekjoon] 19621_회의실 배정 2

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

---

< 회의실 배정 2 >

 

문제 풀이 

 

회의가 끝나는 시간을 기준으로 오름차순으로 정렬 후 dp를 활용해 회의를 진행할 수 있는 최대 인원을 구한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class _19621_ { // 회의실 배정 2
	static class Info {
		private int start;
		private int end;
		private 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());

		ArrayList<Info> list = new ArrayList<>();
		int dp[] = new int[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());

			list.add(new Info(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())));
		}

		Collections.sort(list, new Comparator<Info>() {

			@Override
			public int compare(Info o1, Info o2) {
				return o1.end - o2.end;
			}
		});

		for (int i = 0; i < n; i++) {
			dp[i] = list.get(i).num;
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (list.get(i).start >= list.get(j).end) {
					dp[i] = Math.max(dp[i], dp[j] + list.get(i).num);
				}
			}
		}

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

		System.out.println(result);
	}
}

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

 

회의의 수를 입력받는다. 회의의 수만큼 회의 정보를 입력받아 ArrayList에 저장한다. ArrayList를 회의가 끝나는 시간을 기준으로 오름차순 정렬한다. dp를 각 회의에 참여하는 인원으로 초기화한 후 ArrayList를 살펴보며 현재값과 현재 회의와 겹치지 않는 이전 회의 인원 + 현재 참여 인원 중 최댓값으로 업데이트한다. 최종 dp를 살펴보며 최대 인원을 구해 출력한다.  

---

---