[BOJ][Python]14501 풀이

https://www.acmicpc.net/problem/14501

14501번: 퇴사

from collections import deque

n = int(input())
t = {n+1:(16,16)}
q = deque([(1, 0)])
ans = []
for i in range(1, n+1):
    a, b = map(int, input().split())
    t[i] = (a, b)
while q:
    tmp = q.popleft()
    c, d = t[tmp[0]]
    if tmp[0]+c <= n+1:
        q.append((tmp[0]+c, tmp[1]+d))
    else:
        ans.append(tmp[1])
    if tmp[0]+1 <= n+1:
        q.append((tmp[0]+1, tmp[1]))
    else:
        ans.append(tmp[1])
print(max(ans))

시간표를 짜는 문제와 유사하지만 약간 다른 그런 문제입니다. 문제를 읽어보면 dp나 그리디겠거니 싶다가 n 범위와 시간제한을 보면 브루트포스로도 풀겠네 싶은 생각이 드는 문제입니다. 그래서 저는 bfs를 풀듯이 브루트포스로 풀어봤습니다. 제한조건이 없이 전부 q에 넣는 방식이기 때문에 불필요한 계산도 많이 해야하고 딕셔너리를 사용하기 때문에 키에러에도 주의해야 합니다.

 

위에서도 언급을 했지만 입력 조건과 시간 제한이 굉장히 넉넉하기 때문에 브루트 포스로 풀어도 충분히 여유로운 문제입니다. q에 추가하는 조건은 해당 날짜에 상담을 선택을 할지 말지에 대해서만 고려합니다. 예를 들어서 첫날에 4일짜리 상담을 배정하면, q에 시간과 수입을 추가하고 해당 상담을 배정하지 않았을 경우를 날짜+1과 0원으로 추가하는거죠. 그걸 n일까지 반복하면 모든 날짜에 대해서 2개씩 q에 삽입이 되므로 n이 15니까 최대 32768번의 연산이 일어나겠네요. 다만 이중 리스트를 이용해서 dp로 푼다면 브루트 포스에 비해 불필요한 연산을 확 줄일 수 있을 것 같습니다.