[Python] 백준 14501: 퇴사 - brute force

문제

14501번: 퇴사

풀이

브루트포스로 각 날짜마다 상담을 받는경우/안받는 경우 나눠서 큐에 넣었다.

 

import sys
import copy
from collections import deque

N = int(sys.stdin.readline())
T = []
P = []

# N번 돌며 인풋 저장
for _ in range(N):
    t, p = map(int, sys.stdin.readline().split(" "))
    T.append(t)
    P.append(p)

# 큐 생성
queue = deque()

# 큐에 초기값 넣어주기
# 배열: 오늘까지 날짜별로 번 돈 (여러 날에 걸쳐 상담을 진행할 경우 첫날에 금액을 저장)
# 인덱스: 오늘의 날짜
queue.append([[0 for _ in range(N)], 0])

# 최종 결과값이 될 애
result = 0

# 큐가 빌때까지
while queue:
    arr, index = queue.popleft()

    # 오늘의 날짜가 이미 퇴사일이거나 넘었을 경우
    if index >= N:
        # 최대값 갱신해주기
        result = max(result, sum(arr))
    else:
        # (마지막날이 아닌 경우에만) 오늘의 상담을 잡지 않고 인덱스(날짜)만 하나 높여서 큐에 넣어줌
        if index != N-1:
            queue.append([copy.deepcopy(arr), index+1])

        # 오늘 들어온 상담 소요시간이 퇴사일을 넘을 경우
        if index+T[index] > N:
            # 최대값 갱신해주기
            result = max(result, sum(arr))
        else:
            newarr = copy.deepcopy(arr)
            
            # 첫날 금액 저장하기
            newarr[index] = P[index]
            
            # 배열과 인덱스(방금 받은 상담 끝나는날)를 큐에 넣기 
            queue.append([newarr, index+T[index]])

print(result)