백준 14501 퇴사 파이썬

백준 14501번 퇴사 풀이

접근방식

1. 상담시간과 금액을 입력받기
2. 상담시간을 기준으로 금액을 누적해서 dp에 저장
3. 이때, 상담기간이 퇴사일을 넘길 경우, 해당 날짜에는 상담을 하지 않는다는 의미로,
   dp[i] = dp[i+1]을 해준다.
4. 상담이 가능한 경우, 해당 날짜 이전까지 누적된 금액과 상담할 경우 받게 될 금액의 합을 비교한다.
5. 최종적으로 dp[0]을 출력함으로써 리스트 탐색을 마친다.

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

# 상담이 걸리는 시간
T = []
# 금액
M = []

dp = [0] * (n+1)

for _ in range(n):
    t, m = map(int, input().split())
    T.append(t)
    M.append(m)

# 리스트의 역순으로 진행
for i in range(n-1, -1, -1):
    # i일에 상담을 하는 것이 퇴사일을 넘기면 상담 x
    if i + T[i] > n:
      # 상담을 하지 않기 때문에 바로 이전인 i+1을 가져온다.
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1] , dp[i + T[i]] + M[i])
print(dp[0])

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

다이나믹 프로그래밍의 개념을 잘 적용할 수 있는 문제라고 생각합니다.

이 문제를 3번 정도 풀었는데 풀 때마다 헷갈리는 부분이 생겼었지만,

헷갈리던 부분도 계속 풀다보니 해결할 수 있었습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다. Just do it & Keep steady