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

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

15486번: 퇴사 2

 

---

• 문제
• 소요시간: 24분 30초

---

• 설계하기(접근방법) 

1. 입력받기

회의 리스트를 입력받는다

 

2. 구현하기

dp를 구현 할 때 

 

dp[현재 날짜 + 상담 소요날짜]의 날의 돈이

현재 날짜의 돈 + 상담 돈보다 작으면

갱신해준다

 

주의해야 하는점은, 우리는 회의를 미래를 위해서 하지 않을 수도 있다

즉 dp 값을 갱신할 때 항상 이전의 최대값으로 갱신을 해준 다음

dp 연산을 진행해주어야 한다

 

 

3. 출력하기

max(dp)를 출력한다

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n = int(input())

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

print(max(dp))

---

• 얻어갈 부분

1. 어려운 dp 문제는 항상 까다로운 조건이 하나 이상 있다. 깊게 생각하자