[BOJ] 14501 퇴사_DP

퇴사

link

내 풀이

• 방식 : DP, BFS
• 날짜를 하루씩 늘려가거나, 상담을 진행하여 이후 날짜로 이동
• DP를 퇴사하기 전 날짜수로 1차원 리스트
• DP에 날짜별 금액을 저장
• 해당 날짜의 금액과 DP에 저장되어 있는 금액 준 큰 값을 DP에 업데이트

📰code

from collections import deque

# 입력
n = int(input())
schdl = []
for _ in range(n):
    schdl.append(list(map(int,input().split())))
schdl.append([0,0])

# 초기 설정
dp = [-1]*(n+1)
q = deque()
q.append((0,0))
answer = 0

# BFS
while q:
    day,s = q.popleft()
    if dp[day]>=s: # 기존 날짜까지 올 수 있는 가장 큰 비용으로 산출, 동일한 날짜에 비용이 적은 경우는 제외시킴
        continue
    else: 
        dp[day]=s # 큰 비용으로 Update
        if day+1 < n: # 상담을 안하고 넘어가는 날
            q.append((day+1,s))
        if day+schdl[day][0] <= n: # 상담을 하는 날, 퇴사날까지 포함하여야 마지막 상담까지 받을 수 있음
            q.append((day+schdl[day][0],s+schdl[day][1])) # 상담을 하면 상담한 날짜 동안 이동
        answer = max(answer,s) # 가장 큰 비용으로 업데이트
print(answer)

다른 풀이

• 방식 : DP, Greedy
• 점화식을 활용하여 논리적으로 전계함

📰code

N = int(input())
time_price = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1): # 뒤에서부터 마지막 날짜부터 금액들 더해감
    if i + time_price[i][0] <= N: # 상담이 끝나는 시점이 N보다 작은 경우를 확인함
        dp[i] = max(dp[i+1], time_price[i][1] + dp[i + time_price[i][0]]) # 받을 수 있는 경우를 greedy형식으로 풀어냄
    else:
        dp[i] = dp[i+1]

print(dp[0])

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡