[백준] 19621 회의실 배정 2 파이썬

문제 링크 : www.acmicpc.net/problem/19621

 

처음 접근한 방법은 완전탐색 알고리즘이였습니다.

 

가능한 경우의 수를 나열해보자는 방식이였는데, 경우의 수를 알아야 나열할 수 있는데

 

자꾸 재귀적으로 짤 수 밖에 없었고, 방법이 잘못되었단 생각이 들었습니다.

 

결국 실패해서 검색해보고 접근방법을 깊이우선탐색(DFS)로 변경하여 배웠습니다.

 

[참고]

[1]: jinho-study.tistory.com/926,

[2]: txegg.tistory.com/138

푸는 방법

각 시간을 기준으로 잡았을 때 가능한지를 탐색해야 합니다.

 

1. 알고리즘 상의 탐색할 데이터의 끝을 설정하여, 끝에 다가갔다면 마지막 값을 리스트에 담습니다.

 

2. 끝이 아니라고 생각하면, 현재 값을 계속 추가해가며 더합니다.

 

3. 반환된 값들의 중 최고 값을 반환합니다.

N = int(input())
meetings = []
for _ in range(N):
    meetings.append(tuple(map(int, input().split())))

meetings.sort()
peoples = []
last_start = max([s for s,e,p in meetings])

def dfs(x, current):
    current += meetings[x][2]
    if meetings[x][1] > last_start:
        peoples.append(current)
    for i in range(x+1, N):
        if meetings[x][1] > meetings[i][0]:
            continue
        dfs(i, current)

for i in range(N):
    dfs(i, 0)
print(max(peoples))