[Algorithm] 15486번 - 퇴사2

오답노트

2024.07.25 (목)
https://www.acmicpc.net/problem/15486

• i가 0인 경우부터 n-1인 날에 있는 n개의 상담을 모두 고려하기 위해 dp 테이블을 리스트 크기를 넉넉하게 잡았다. 위의 예시는 dp테이블이 dp[9] 까지만 변경되기 때문에 i=9 까지만 나타냈지만, 실제 선언한 dp 테이블의 크기는 n에 t의 최댓값인 50을 더하면 된다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

• 점화식 : dp 테이블에는 i일까지 상담을 했을 때 벌 수 있는 최대 수익을 저장한다
  dp[i] = i일 까지의 최대 수입
  

• i에 있는 상담을 진행하는 경우와 진행하지 않는 경우를 고려하여 문제를 풀었다. 이 때 상담이 가능한 다음 날짜의 dp테이블을 변경해주었다.

  • i일에 상담을 하는 경우, 다음 상담이 가능한 날은 i+t[i] 이후이다.
    i일의 상담을 마친 후 최대 수입 dp[i+t[i]] = max(dp[i+t[i]], dp[i-1]+p[i])
  • i일에 상담을 하지 않는 경우, 다음 날인 i+1 부터 상담이 가능하다.
    dp[i+1] = max(dp[i], dp[i+1])

i=0 번째 상담 유무에 따른 dp 테이블 변화

파란색 : i=0 의 상담을 진행한 경우
빨간색 : i=0 의 상담을 진행하지 않은 경우

i=1 번째 상담 유무에 따른 dp 테이블 변화

파란색 : i=1 의 상담을 진행한 경우
빨간색 : i=1 의 상담을 진행하지 않은 경우

i=2 번째 상담 유무에 따른 dp 테이블 변화

• i=2의 상담을 진행하는 경우, 다음 상담 가능 날은 i=3 이 된다.
  이 때, dp[3] = max(dp[3], dp[2]+p[2]) 인데 두 값이 모두 10이어서 dp[3]=10 이다.
• i=2의 상담을 진행하지 않는 경우, 다음 상담 가능 날은 i=3 이다.
  이 때에도, dp[3] = max(dp[3], dp[2]) 로 10이 된다.
  상담을 진행하는 경우와 아닌 경우 모두 dp[3]=10 이다.

i=3 번째 상담 유무에 따른 dp 테이블 변화

• i=3의 상담을 진행하는 경우, 다음 상담 가능 날은 i=4 이고,
  이 때 dp[4] = max(dp[4], dp[3]+p[3]) = 30 이 된다.
• 반면에 상담을 진행하지 않을 경우에도 상담 가능 날은 i=4 이지만, i=3의 상담을 진행하는 경우의 수입이 더 크기 때문에 dp[4]는 30이 된다.

i=4 번째 상담 유무에 따른 dp 테이블 변화

파란색 : i=4 의 상담을 진행한 경우
빨간색 : i=4 의 상담을 진행하지 않은 경우

---

i=5 번째 상담 유무에 따른 dp 테이블 변화

• 파란색 : i=5 의 상담을 진행한 경우
• 빨간색 : i=5 의 상담을 진행하지 않은 경우

---

i=6 번째 상담 유무에 따른 dp 테이블 변화

파란색 : i=6 의 상담을 진행한 경우
빨간색 : i=6 의 상담을 진행하지 않은 경우

---

주의) 파이썬의 경우 빠른 입출력을 위한 코드가 필수적인 듯 하다.

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())

https://www.acmicpc.net/board/view/22716

전체 코드

# 동적 프로그래밍 - 15486번 - 퇴사2
import sys
input = sys.stdin.readline

n = int(input())
t = [0] * n
p = [0] * n
for i in range(n):
    t[i], p[i] = map(int, input().split())
dp = [0 for _ in range(n+50)]

for i in range(n):
    dp[i + t[i]] = max(dp[i+t[i]], dp[i]+p[i])      # i번째 날에 잡힌 일을 하는 경우
    dp[i+1] = max(dp[i], dp[i+1])                   # i번째 날에 잡힌 일을 하지 않는 경우

print(dp[n])