[백준 19621] 회의실 배정 2 [Java]

문제

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

 

---

풀이

N개의 회의실 정보와, 회의 참여 인원이 시간 순서대로 주어졌을 때

회의를 진행할 수 있는 최대 인원을 구하는 문제다.

문제에서는 K번째 회의는 K - 1, K + 1번째 회의와 시간이 겹치지만, 다른 회의와는 시간이 겹치지 않는다고 명시되어있다.

dp로 쉽게 풀이할 수 있다.

dp[i] : i 번째 회의까지 참석 가능한 최대 인원 수

dp[i - 2]에 현재 회의를 진행하는 것과, dp[i - 1]을 그대로 진행하는 것 중 선택하면 된다.

따라서 점화식은 다음과 같다.

dp[i] = max(dp[i - 1], dp[i - 2] + 1)

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

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/19621.java