BOJ 19621번: 회의실 배정2

www.acmicpc.net/problem/19621

19621번: 회의실 배정 2

• 임의의 회의 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)