[파이썬] 백준 퇴사

14501번: 퇴사

---

나의 풀이

• 오랜만에 푸는 DP 문제이다. 고민하다가 못 풀어서 결국 풀이를 참고했다.
• 각 날짜 별 최대 이윤을 DP 테이블로 구성하고, 최대 이윤 값을 얻을 땐 뒤쪽 날짜부터 거꾸로 진행해서 계산해야 한다.
• 이렇게 되면 DP[i] = max(현재 상담 일자의 최대 이윤 + 현재 상담이 끝난 후를 기준으로 한 최대 이윤, 기존 최댓값)으로 표현이 가능하다. 

n = int(input()) # 전체 상담 개수
t_list = [] # 상담 완료까지 기간
p_list = [] # 상담 완료 시 받을 수 있는 금액

dp = [0] * (n + 1)
max_value = 0

for _ in range(n):
    t, p = map(int, input().split())
    # 원소 추가
    t_list.append(t)
    p_list.append(p)

# DP 테이블 작성
for i in range(n - 1, -1, -1):
    time = t_list[i] + i
    # 상담이 기간 안에 끝나는 경우
    if time <= n:
        dp[i] = max(p_list[i] + dp[time], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

참고

이것이 취업을 위한 코딩 테스트다 with 파이썬