14501

날짜 : 2023. 04. 14

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
t = list()  # 소요기간
p = list()  # 보수
dp = [0 for _ in range(n+1)]  # 현재 보수, 완료일

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())  # 입력
    t.append(a)
    p.append(b)

for i in range(n-1, -1, -1):  # 역순으로 진행
    if t[i] + i > n:  # 상담에 필요한 일수가 퇴사일 초과
        dp[i] = dp[i+1]  # 다음날 값 그대로 가져옴
    else:
        dp[i] = max(dp[i+1], dp[t[i] + i] + p[i])  # 금액 갱신
    #print(dp)
print(dp[0])

 

 

풀이

- 다이나믹 프로그래밍을 활용하여 풀이한다.

- 역순으로 진행, 해당 인덱스의 상담 날짜가 범위에 포함되지 않는 경우 (i+1)의 값으로 갱신하고, 포함되는 경우 해당 날짜의 상담을 잡았을 때의 누적합을 비교함으로써 갱신한다.

 

 

알게된 점

- bottom-up 방식으로 풀이하려 했는데 계속 맨 마지막 인덱스의 값이 갱신되지 않아 풀이를 참고했고, 역순으로 풀이했다.

 

 

참고 사이트

- https://yuna0125.tistory.com/124

[백준🥈3] #14501 퇴사 (python)