[baekjoon] 백준 14501번(파이썬): 퇴사

문제

14501번: 퇴사

알고리즘

- 반복문을 통해 퇴사하기 전날부터 현재까지 확인한다.

- 상담 기간이 퇴사 이후 까지라면 현재 상담 비용은 이후의 비용이 된다.

- 퇴사 이전에 상담이라면 현재 상담 비용 + 현재 상담을 끝낸 후 비용과 상담을 받지 않는 비용일 비교하여 더 큰 값을 현재 비용이 된다.

코드

import sys

n = int(sys.stdin.readline())
m = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [0] * (n + 1)

# 반복문을 통해 퇴사하기 전날부터 현재까지 확인
for i in range(n - 1, -1, -1):
    # 상담 기간이 퇴사 이후까지라면
    # 현재 상담 비용은 이후의 비용이 든다.
    if i + m[i][0] > n:
        dp[i] = dp[i + 1]

    # 퇴사 이전에 상담이라면
    # 현재 상담 비용 + 현재 상담을 끝낸 후 비용과 상담을 받지 않는 비용을 비교
    else:
        dp[i] = max(m[i][1] + dp[i + m[i][0]], dp[i + 1])

print(dp[0])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법