[알고리즘/DP] 14501번 : 퇴사 - python

링크 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

---

• 문제
• 소요시간: 23분 20초

---

• 설계하기(접근방법) 

1. 입력받기

상담 소요시간과 상담 금액을 입력받는다

 

2. 구현하기

이 문제는 2가지 방법으로 풀 수 있다

1. 앞에서 부터 상담리스트를 순회하는 경우

현재 날짜 + 상담소요날짜의 dp에

저장된 값보다 지금 누적상담가격이 높은 경우

지금 값으로 바꿔준다

 

상담을 하지않고 pass하는 경우가 있으므로

현재까지 누적상담가격 중

가장 큰 가격을 현재로 이전해준다

 

2. 리버스 방법

거꾸로 상담이 가능한지 검사한다

상담이 가능한 경우

 

현재 날짜의 상담 가격 + (현재 날짜+상담 소요 날짜)의 가격과

(지금까지 리버스로 순회하면서 )가장 큰 가격을 비교한다

후자가 크다면 상담을 하지 않는 것이 이득이고

전자가 크다면 상담을 진행하는 것이 이득이다

 

 

3. 출력하기

최대값을 출력한다

 

---

• 코드(출력)

n = int(input())

consult_list = [0]
dp = [0 for _ in range(n + 2)]
for i in range(1, n + 1):
    day, cost  = map(int,input().split())
    dp[i] = max(dp[:i + 1])
    if i + day <= n + 1:
        if dp[i + day] < dp[i] + cost :
            dp[i + day] = dp[i] + cost

print(max(dp))

 

---

• 얻어갈 부분

1. 앞에서부터 풀었지만 풀이가 보이지 않는 경우 dp나 그리디는 역순으로 생각해보자