[python] 백준 14501 번 퇴사

백준 14501 번 퇴사

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

문제

풀이

n = int(input())

t = []  # 각 상담에 걸리는 시간
p = []  # 각 상담의 이익

# 상담 정보 입력
for _ in range(n):
    t1, p1 = map(int, input().split())
    t.append(t1)
    p.append(p1)

# DP 테이블 초기화
dp = [0] * (n + 1)

# DP 계산
for i in range(n):
    # 먼저 상담을 선택하지 않을 경우 (이전까지의 최대 이익을 그대로 넘김)
    dp[i + 1] = max(dp[i + 1], dp[i])

    # 상담이 끝나는 날짜가 퇴사일을 넘지 않는 경우에만 상담을 선택
    if i + t[i] <= n:
        dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i])

# 최종적으로 얻을 수 있는 최대 이익 출력
print(dp[n])

n = 7
t = [3, 5, 1, 1, 2, 4, 2]
p = [10, 20, 10, 20, 15, 40, 200]
이라 하고 코드가 어떻게 동작하는 지 알아보자.

첫 번째 상담: 3일 동안 이익 10
dp = [0, 0, 0, 10, 0, 0, 0, 0]

두 번째 상담: 5일 동안 이익 20
dp = [0, 0, 0, 10, 0, 20, 0, 0]

세 번째 상담: 1일 동안 이익 10
dp[4] = dp[3] + 10 → dp[4] = 20
dp = [0, 0, 0, 10, 20, 20, 0, 0]

네 번째 상담: 1일 동안 이익 20
dp[5] = dp[4] + 20 → dp[5] = 40
dp = [0, 0, 0, 10, 20, 40, 0, 0]

다섯 번째 상담: 2일 동안 이익 15
dp = [0, 0, 0, 10, 20, 40, 0, 55]

여섯 번째와 일곱 번째는 퇴사일까지 끝낼 수 없어 선택할 수 없다.