반응형
💻 Problem
서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.
💡 Approach
임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.
문제에서 이런 조건이 주어진다.
어떤 한 회의는 이전 회의와 다음 회의와 겹친다.
따라서 회의를 선택하는 경우는 이전 회의를 듣고 현재 회의를 안 듣거나 / 이전 회의를 안 듣고 현재 회의를 듣거나이다.
dp에 현재 회의의 회의 인원을 저장한다.
이전 회의를 듣고 현재 회의를 안 듣는 경우의 인원(`dp[i - 1]`)과
이전 회의를 안 듣고, 즉, 전전 회의까지의 최댓값에서 현재 회의를 듣는 경우의 인원을 더한 값(`dp[i - 2] + K[i][2]`)을 비교한다.
✏️ Solution
import sys
input = sys.stdin.readline
N = int(input())
K = [list(map(int, input().split())) for _ in range(N)]
K.sort()
dp = [0] * N
dp[0] = K[0][2]
for i in range(1, N):
dp[i] = max(dp[i - 1], dp[i - 2] + K[i][2])
print(dp[-1])
반응형