[G5] 백준 15486 - 퇴사 2 (Python3)

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

15486번: 퇴사 2

이 문제는 백준 퇴사(14501)와 같은 알고리즘으로 동작하는 문제이며, 이 해결방법으로도 14501번 문제를 통과할 수 있습니다.

---

해결방법

다이나믹 프로그래밍으로 해결했다. 이 문제는 마지막 날 부터 상담 건을 진행하면서 '이 날 근무하면 벌 수 있는 최대 금여'를 구하면 해결 할 수 있다.

풀이👀

문제에서 제공하는 예제로 풀이를 진행해보겠습니다.

	1일(index: 0)	2일 (1)	3일 (2)	4일 (3)	5일 (4)	6일 (5)	7일 (6)
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200

해결방법에 나온 것처럼 점화식은 아래와 같다.

①... $(i+t  \leq  N),  d_i = max(d_{i+t} + p_i, d_{i+1})$

②... $(i+t >  N), d_i = d_{i+1}$

 

dp table의 i번째 elemtary는 i+t번째의 값과 i일 차의 급여의 합이다. 대신에 i+t일이 퇴사날을 넘어가면(N보다 크면) i일 차의 급여는 i+1과 같이 한다. 

1. dp table 초기화

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	0	0	0	0	0	0

 dp table은 길이가 n+1 만큼 만들고 0으로 모두 초기화 한다. 

 

2-1. 7일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	0	0	0	0	$d_7$	0

n = 7이므로 7일차부터 1일차까지 동작한다. 7일차 상담 일정은 2일이나 걸려서 퇴사날짜보다 길어지기 때문에 상담하지 않는다.

$d_6$은 $i + T_i  \leq N$에 대해서 $6+2  \leq 7$ 이므로 ② 조건에 의해 $d_6$ = 0

 

2-2. 6일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	0	0	0	$d_6$	0	0

$5+4 >  7$ 에 의해서 ② 조건에 만족하므로 $d_5 = d_6$이다.

 

2-3. 5일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	0	0	$max(0+15, 0) = 15$	0	0	0

$4+2 \leq 7$에 의해서 ①조건에 만족하므로 $d_4 = max(0+15, 0) = 15$ 이다.

 

2-4. 4일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	0	$max(15+20, 15) = 35$	15	0	0	0

$3+1 \leq 7$에 의해서 ①조건에 만족하므로 $d_3 = max(d_4+p_3, d_4) = max(15+20, 15) = 35$이다.

 

2-5. 3일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	0	$max(35+10, 35) = 45$	35	15	0	0	0

$2+1 \leq 7$에 의해서 ①조건에 만족하므로 $d_2 = max(d_3+p_2, d_3) = max(35+10, 35) = 45$이다.

 

2-6. 2일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	0	$max(0+20, 45) = 45$	45	35	15	0	0	0

$1+5 \leq 7$에 의해서 ①조건에 만족하므로 $d_1 = max(d_6+p_1, d_2) = max(0+20, 45) = 45$이다.

 

2-7. 1일차부터 상담하면 벌 수 있는 최대 금액

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	$max(35+10, 45) = 45$	45	45	35	15	0	0	0

$0+3 \leq 7$에 의해서 ①조건에 만족하므로 $d_0 = max(d_3+p_0, d_1) = max(35+10, 45) = 45$이다.

 

3. 최종 dp table

	$d_0$	$d_1$	$d_2$	$d_3$	$d_4$	$d_5$	$d_6$	$d_7$
MONEY	45	45	45	35	15	0	0	0

dp table은 최종적으로 위와 같은 형태로 만들어질 것이다. 여기서 최댓값이 정답이므로 최댓값을 출력한다.

---

코드🐱‍👓

N = int(input())
arr = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (N+1)
for i in range(N-1, -1, -1):
    t, p = arr[i]
    if i+t > N:
        dp[i] = dp[i+1]
        continue
    dp[i] = max(dp[i+t] + p, dp[i+1])
print(max(dp))

코드 설명

arr에는 튜플 형태로 (상담 시간 t,  수익 p)가 입력된다.

---