[python/파이썬] 백준 10622 회의실 배정 3

[문제 출처]

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

19622번: 회의실 배정 3

 

 

[문제 풀이]

 

다른 회의실 배정 문제와 다른 점은 많은 회의를 하게 하는 게 아닌 많은 사람이 회의에 참여할 수 있게 하는 것이다.

회의 시간도 신경써야하고 인원수도 신경 써야 하기에 너무 복잡하다고 생각했는데

주어진 문제의 조건을 잘 살펴보지 않은 탓에 더 복잡하게 이해하고 있었다.

 

k번째 회의의 시간은 k-1번째 회의와만 겹치기에 그 부분만 신경 써주면 어렵지 않게 풀 수 있다.

오히려 시작 시간과 종료시간은 거의 신경 쓸 것 없고 인원수만 신경쓰면 되는 문제이다.

import sys
input = sys.stdin.readline

n = int(input())

times = []
for _ in range(n):
    s, e, p= map(int, input().split())
    times.append([s,e,p])


dp = [0 for _ in range(n)]

for i in range(n):
    if i==0:
        dp[i] = times[i][2]
    elif i==1:
        dp[i] = max(times[i][2], dp[i-1])
    else:
        dp[i] = max(dp[i-2] + times[i][2], dp[i-1])

print(dp[n-1])