[backjoon] 14501 퇴사 (python)

문제 14501번: 퇴사

BruteForce 문제 | dynamic programming 문제

이 문제는 상담원으로 일하고 있는 백준이가 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 해서 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하는 문제이다.

• Ti - 상담을 완료하는데 걸리는 기간
• Pi - 상담을 했을 때 받을 수 있는 금액

• 1일에 일하면 4일, 5일 일할 수 있음 -> 💰: 10 + 20 + 15 = 45
• 2일에 일하면 2일만 일할 수 있음 -> 💰: 20
• 3일에 일하면 4일, 5일 -> 💰: 10 + 20 + 15 = 45
• 4일에 일하면 5일 -> 💰: 20 + 15 = 35
• 5일에 일하면 5일 -> 💰: 15
• 6, 7일은 일하는 날짜에 초과 되므로 계산 불가

위의 사진에서 퇴사 전에 할 수 있는 최대 상담 날짜는

• 1일, 4일, 5일
• 3일, 4일, 5일
  이 두 가지 경우이고, 이때의 이익은 10+20+15=45이다.

---

문제풀이

dynamic programming 기법을 사용하여 문제를 해결

여기서 dynamic programming 기법이란?
👉 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법
여기에서는

• 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않기
• (당일 일을 맡았을 때 들어오는 금액 + 일을 끝낸 뒤 다음 상담 금액) vs (다음 날 일했을 때 얻을 수 있는 금액)
  이 두 개로 문제를 나누어서 풀면 된다!

---

입력값들을 받아오는 코드

import sys
input = sys.stdin.readline
N = int(input())

timeTable = [list(map(int,sys.stdin.readline().split())) for i in range(N)]
# timeTable = [[3, 10], [5, 20], [1, 10], [1, 20], [2, 15], [4, 40], [2, 200]]

dp = [0 for i in range(N+1)]
# 값 비교를 위해서 N + 1

여기서는 기간과 금액이 timeTable[i][0] 과 timeTable[i][1] 이다.

• T - 상담을 완료하는데 걸리는 기간 : timeTable[i][0]
• P - 상담을 했을 때 받을 수 있는 금액 : timeTable[i][1]

우선 문제의 뒤에서 부터 접근한다

  for i in range(N-1,-1,-1):

1. 상담이 끝나는 날이 n을 넘어가게 되면 일을 맡을 수 없기 때문에

ex) 표에서 상담 날짜 6일이 상담을 완료하는 데 걸리는 기간은 4일이다. 여기서 백준이의 퇴사 날짜는 7일 이므로 일을 맡을 수 없다!!!

• 오늘 날짜: 6 + 상담을 완료하는데 걸리는 기간: 4 > 퇴사일 : 7

   # 오늘 날짜 + 상담을 완료하는데 걸리는 기간 > 퇴사일
    if i + timeTable[i][0] > N:
    # 여기서 dp[i] = 0 이 아닌 dp[i] = dp[i+1]되어야 하는 이유는?
    # 누적되는 이익을 구하기 때문이다!
        dp[i] = dp[i+1]

2. 그 외의 부분에는 아래를 비교해서 큰 값을 구하면 된다!
(1) 당일 일을 맡았을 때 들어오는 금액 + 일을 끝낸 뒤 다음 상담 금액
(2) 다음 날 일했을 때 얻을 수 있는 금액

ex)

• 상담 날짜가 4일 일때 즉, i = 3일때 상담을 완료하는데 걸리는 기간은 1일이고, 금액은 20인 경우는 아래와 같이 계산된다.
  max(20 + dp[3+1], dp[4]) ➔ max(20 + 15, 15) ➔ max(35, 15) ➔ 35
  이 경우에는 당일 일을 맡는 게 이득이다!

• 상담 날짜가 2일 일때 즉, i = 1일때 상담을 완료하는데 걸리는 기간은 5일이고, 금액은 20인 경우는 아래와 같이 계산된다.
  max(20 + dp[1+5], dp[2]) ➔ max(20 + 0, 45) ➔ max(20, 45) ➔ 45
  이 경우에는 다음 날 일하는 것이 이득이다!
  

    else:
    # 1) 당일 일을 맡았을 때 들어오는 금액 + 일을 끝낸 뒤 다음 상담 금액 
    # -> timeTable[i][1] + dp[i + timeTable[i][0]]
    # 2) 다음 날 일했을 때 얻을 수 있는 금액
    # -> dp[i+1]
        dp[i] = max(timeTable[i][1] + dp[i + timeTable[i][0]], dp[i+1])

전체코드

import sys
input = sys.stdin.readline

N = int(input())

timeTable = [list(map(int,sys.stdin.readline().split())) for i in range(N)]

dp = [0 for _ in range(N+1)]

# 상담을 완료하는데 걸리는 기간 : timeTable[i][0] 
# 상담을 했을 때 받을 수 있는 금액 : timeTable[i][1]
for i in range(N-1,-1,-1):
    if i + timeTable[i][0] > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(timeTable[i][1] + dp[i + timeTable[i][0]], dp[i+1])

print(dp[0])

---

출처 [백준/14501번/파이썬(Python)] 퇴사 / DP
출처 [백준] 14501번(python 파이썬)