⚡️ baekjoon. 14501 퇴사 [Silver III][python]

 

관련 풀이를 봤을때 탐욕법으로 접근해야 하나 하다가, 주어진 예시 케이스로 도저히 접근할 수가 없어서,

dfs로 접근해서 모든 경우의 수에 대해 가지고 있다가 최댓값을 보여주는 접근 방식을 택했다. 

N = int(input())

results = list()

# history 변수는 debug 용도 
def dfs(start, current, history):
    if (start >= len(meetingList)):
        results.append(current)
        return
    
    # 오늘 잡혀있는 미팅을 진행할 경우 
    next = start + meetingList[start][0]
    if (next <= len(meetingList)):
        dfs(next, current + meetingList[start][1], history + str(start))
    
    # 오늘 잡혀있는 미팅을 진행하지 않을 경우 
    for i in range(start + 1, next):
        dfs(i, current, history)
    

meetingList = list()
for _ in range(N):
    meetingList.append(list(map(int, input().split())))

dfs(0, 0, '')
results.sort()
print(results[-1])

 

+) 다른 풀이로는 동적 dp로 접근하는 방법이 있을 것 같다. 

https://zu-techlog.tistory.com/42

[BOJ] 백준 14501번 퇴사 - 파이썬(Python)