[BOJ] 14501. 퇴사

문제

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

14501번: 퇴사

 

돈미새 백준이..

---

 

주요 아이디어

풀 때마다 항상 느끼지만 DP 문제는 정말 아이디어가 중요한 것 같다..

• 앞에서 (i=1) 부터 접근하지 말고, 맨 끝 날짜부터 접근해보자
• 매 상담에 대해 현재 상담일자의 이윤 + 현재 상담을 마친 일자로부터의 최대 이윤 계산
• 즉 dp[i] = i번째 날 ~ n번째 날까지 낼 수 있는 최대 이익이다

 

 

예제 살펴보기

 

• 7일차에는 상담이 불가하다
  • 상담 소요 일자 + 현재 일자 =  2 + 7 > n 이기 때문이다
  • dp[7] = 0, max_value = 0
• 6일차에도 상담이 불가능하다
  • 상담 소요 일자 + 현재 일자 =  4 + 6 > n 이기 때문이다
  • dp[6] = 0, max_value = 0
• 5일차부터 상담이 가능해진다
  • 상담 소요 일자 + 현재 일자 = 2 + 5 >= n 이기 때문이다
  • dp[5] = 15, max_value = 15
• 4일차
  • 상담 소요 일자 + 현재 일자 = 1 + 4 >= n 이기 때문이다
  • dp[4] = max(p_list[4] + dp_list[4+t_list[4]], max_value) = 20 + 15 = 35
  • max_value = 35
• 3일차
  • 상담 소요 일자 + 현재 일자 = 1 + 3 >= n 이기 때문이다
  • dp[3] = max(p_list[3] + dp_list[3+t_list[3]], max_value) = 10 + 35 = 45
• 2일차
  • 상담 소요 일자 + 현재 일자 = 1 + 3 >= n 이기 때문이다
  • dp[2] = max(p_list[2] + dp_list[2+t_list[2]], max_value) = 20 + 0 = 20
  • max_value = 45
• 1일차
  • 상담 소요 일자 + 현재 일자 = 1 + 3 >= n 이기 때문이다
  • dp[1] = max(p_list[1] + dp_list[1+t_list[1]], max_value) = 10 + 20 = 30
  • max_value = 45

 

---

 

코드 구현 (Python 3)

 

# 입력 받기

n = int(input())
t_list = [0 for _ in range(n)]
p_list = [0 for _ in range(n)]

for i in range(n):
    t, p = map(int, input().split())
    t_list[i] = t; p_list[i] = p

dp_max = [0 for _ in range(n+1)]
max_value = 0 # 현재까지의 최대값

for i in range(n-1, -1, -1):
    # 상담에 걸리는 시간
    time = t_list[i] + i

    # 상담에 걸리는 시간이 적으면
    if time <= n:
        # 현재 꺼 vs max_value
        dp_max[i] = max(p_list[i] + dp_max[time], max_value)
        max_value = dp_max[i]
    
    else:
        dp_max[i] = max_value

print(max_value)

 

---

 

 

제출 결과

---

 

코드 개선 방안

항상 DP는 아이디어를 떠올리는 것이 어려운 것 같다.

최대한 다양한 문제를 접해보고, 점화식을 잘 세우는 습관을 들이자!