백준|14501번|퇴사

문제설명
상담원으로 일하는 백준이 일정 기간동안 일해서 최대한 벌 수 있는 금액을 구하는 문제입니다. 상담은 1일에서 그 이상이 걸릴 수 있고 다른 상담을 하는 동안에는 새로운 상담을 할수 없습니다.

작동 순서
1. 기간 N을 입력받습니다.
2. 각 상담들의 보수와 기간을 입력받습니다.
3. 그 일을 수행할 수 있는 경우 그 일을 수행하는 것을 큐에 추가합니다.
4. 그 일을 수행할 수 없는 경우 그 일을 무시합니다.
5. 일을 수행할 수 있어도 그 일을 무시하는 경우를 큐에 추가합니다.
6. 모든 일정이 끝나고 얻을 수 있는 최대의 이익을 출력합니다.

소스코드

import sys
from collections import deque
N = int(sys.stdin.readline())
counseling = []
maxMoney = 0
for i in range(N):
    counseling.append(list(map(int, sys.stdin.readline().split())))
work = deque()
work.append([1, 0, 0])
while work:
    day, remain, money = work.popleft()
    if money > maxMoney:
        maxMoney = money
    if day <= N:
        if remain == 0:
            if day+counseling[day-1][0]-1 <= N:
                work.append([day+1, counseling[day-1][0]-1, money+counseling[day-1][1]])
            work.append([day+1, 0, money])
        else:
            work.append([day+1, remain-1, money])
print(maxMoney, end="")

후기
DP문제인데 BFS로 풀어버렸네요. DP는 아직 너무 어렵게 느껴지는 것 같습니다.