[백준] 14501번 퇴사 (Python, DP)

<문제 링크>

백준 14501번 퇴사

---

문제 요약

백준이가 N+1 일째 되는날 퇴사하는데, N일째 날까지 돈을 최대한 많이 벌고싶어 한다.
1~N 까지 각각 소요기간과 페이가 주어질 때, 최대로 벌 수 있는 금액을 구하면 된다.

ex0)

• N = 7
• T(i) : i번째 날 주어지는 업무의 소요기간
• P(i) : i번째 날 주어지는 업무의 페이

	1	2	3	4	5	6	7
T(i)	3	5	1	1	2	4	2
P(i)	10	20	10	20	15	40	200

=> 최대값 : 1, 4, 5일에 일하기. 10 + 20 + 15 = 45

---

문제 풀이

본 문제는 DP 알고리즘을 통해 해결할 수 있다.
다른 사람들은 어떻게 풀었나 찾아보니, 대부분 마지막 날부터 1일차까지 반대로 오던데, 나는 거기까지 생각이 미치지 못해 첫날부터 마지막날까지 순서대로 올라갔다.

이 문제를 풀 때, 가장 중점적으로 생각한 것은 다음 두가지였다.
(M(i) 를 i번째 날에서 최대값으로 설정한다.)

1. T(i) 값이 1인가?
   -> 1이면 M(i) = M(i-1) + P(i) 일 것이다.
2. T(i) 값이 1보다 크면?
   -> M(i)에는 M(i-1)에 0이 더해지겠지만, T[i]일 후에 P[i]가 더해질 것이다.
   -> 이렇게 보면, M(i)도 몇일 전으로부터 더해진 값이 더 클 수도 있을 것이다.

이렇게 생각 전개가 흘러가다 보니, M(i)는 다음 둘 중에 하나로 정해질 것이라 생각하였다.

1. M(i-1)에서 더해지는 경우
   • T(i) == 1 인 경우 : M(i-1) + P(i)
   • T(i) > 1 인 경우 : M(i-1) + 0
2. M(i-1) 보다 더 앞에서 시작할 경우
   • 만약 T(k)일 앞에서 시작할 경우, M(k)를 고려할 때 P(k) 값을 M(i)에 더해주어야 할 것이다.

여기서 2번이 조금 복잡한데, 문제 요약의 예시 ex0)에 적용해보자.

ex0)

	1	2	3	4	5	6	7
T(i)	3	5	1	1	2	4	2
P(i)	10	20	10	20	15	40	200

만약 6일째 되는 날의 최대값에 대해 고민하고 있다고 가정하자.
먼저 "1. M(i-1)에서 더해지는 경우" 이다.

1. M(i-1)에서 더해지는 경우
   • T(6) == 4 > 1 이다.
   • 따라서 이 경우는 M(5)가 된다.
   • M(5)는 45이다.

그 다음, "2. M(i-1) 보다 더 앞에서 시작할 경우" 이다.

2. M(i-1)보다 더 앞에서 시작할 경우
   • 2번째 날에서 시작할 경우, 6번째 날에서 끝난다.
   • 따라서 이 경우는 M(1) + P(2) 가 된다.
   • M(1) + P(2)는 20이다.

여기서 만약, P(2)가 1000 이라면, 이 경우를 골라야 할 것이다.

이제 해당 규칙을 구현해보자.

다양한 구현 방법이 있겠지만, 나는 1번째 날 부터 차례대로 올라가도록 구현하였고, 이는 다음과 같다.

1. "T(i) > 1" or "T(i) == 1" 을 파악하고, 1보다 크면 T(i)일 후에 반영해준다.
   • T(i) > 1 일 경우
     -> M(i-1) + P(i) 값을 T(i)일 후에 넣어준다.
     -> M(i) = max(M(i), M(i-1))
   • T(i) == 1 일 경우
     -> M(i) = max(M(i), M(i-1) + P(i))

여기서 max() 안에 M(i)가 들어가있는 이유는, M(i)도 T(k)일 앞에서 특정 값을 넣었을 수 있으니, 해당 값을 비교해주어야 한다.

---

구현

N = int(input())
T = [0]
P = [0]

for i in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

maxAdvantage = [0]*(N+1)

for i in range(1, N+1):
    todayMax = 0
    if T[i] > 1:
        todayMax = maxAdvantage[i-1]
        if (i + T[i] - 1) <= N:
            if maxAdvantage[i + T[i] - 1] < (todayMax + P[i]):
                maxAdvantage[i + T[i] - 1] = todayMax + P[i]

    else:
        todayMax = maxAdvantage[i-1] + P[i]

    maxAdvantage[i] = max(todayMax, maxAdvantage[i])

print(maxAdvantage[N])

위에서 언급한 규칙들을 그대로 코드로 구현한 것이다.