알고리즘💻/그래프(DFS&BFS)
BOJ 19621번: 회의실 배정2
호프
2021. 5. 12. 00:11
19621번: 회의실 배정 2
서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단,
www.acmicpc.net
- 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.
이 조건 때문에 dfs로 구현하여 풀 수 있다. K번째 회의를 선택하고 K+2번째 회의를 선택하는 경우와 K번째 회의를 선택하지 않고 K+1번째 회의를 선택하는 경우
import sys
sys.setrecursionlimit(10**9)
N = int(sys.stdin.readline())
time = []
ans = 0
for _ in range(N):
time.append(list(map(int, sys.stdin.readline().split())))
def dfs(cnt, tmp):
global ans
if (cnt>N-1):
ans = max(ans, tmp)
return
dfs(cnt+1, tmp)
dfs(cnt+2, tmp+time[cnt][2])
dfs(0,0)
print(ans)