백준 알고리즘 14501번 퇴사 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/14501

14501번: 퇴사

이 문제를 2가지 방법으로 풀었습니다.  DFS(깊이 우선 탐색) 방법과 BFS(너비 우선 탐색)으로 해결하였는데, 

DFS 방법으로 푼 코드는 다음과 같습니다. 

def solution(n, task):
    answer = 0
    # count day money
    # 인덱스 날짜 돈
    stack = [[0, 0, 0]]
    while stack:
        count, day, money = stack.pop()
        #만약 현재 날짜가 지금 위치한 날보다 작을 경우 날짜를 현재 위치한 날로 갱신한다.
        if day<count:
            day=count
        #마지막 날까지 모두 탐색한 경우 answer값과 돈의 크기를 비교하여 answer값을 갱신한다.
        if count == n:
            if money > answer:
                answer = money
       	
        else:
        	# 현재 인덱스의 일을 하였을 때, 최종 날짜안에 할 수 있는지 확인
            if day < count+1 and count + task[count][0] <= n:
                stack.append([count + 1, day + task[count][0], money + task[count][1]])
            # 현재 인덱스의 일을 포함 하지 않았을 경우를 더한다.
            stack.append([count + 1, day, money])
    return answer


n = int(input())
task = []
for _ in range(n):
    a, b = map(int, input().split())
    task.append([a, b])
answer=solution(n,task)
print(answer)