[BOJ] 19621. 회의실 배정 2

www.acmicpc.net/problem/19621

19621번: 회의실 배정 2

문제: 회의실에 최대한 많은 사람들이 회의할 수 있도록 만들어라.

 

문제 이해하기!!

일반 회의실 배정 문제와 다른 문제였습니다.

각 회의마다 인원이 다르고 앞과 뒤의 회의랑 회의시간이 무조건 겹치기 때문에

브루트포스 방법을 쓰는 문제였습니다.

 

---

 

문제에서 시작시간이 순서대로 입력이 들어온다는 말이 없어서

sort()를 해주고 시작했습니다.

dfs를 재귀적으로 썼고

종료 조건은 N보다 n이 커지면서 res보다 val이 클 때로 했습니다.

 

코드:

from sys import stdin
input = stdin.readline

def dfs(n, val):
    global res
    if n >= N and res < val:
        res = val
        return

    for i in range(n, N):
        dfs(i+2, val+arr[i][2])

N = int(input())
arr = [tuple(map(int, input().split())) for i in range(N)]
arr.sort()
res = 0
dfs(0, 0)
print(res)