[백준] 퇴사

문제

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

TC

입력받은 n(날짜)만큼 반복문을 돌면 된다.
O(n)

Idea

최대 이익을 구하기 위해 배열을 역순으로 접근한다는 것이 이 문제의 핵심 아이디어라고 생각한다.

(n-1)번째 인덱스의 날부터 계산하며 (상담을 하게되는 날 + 상담이 지속되는 날)의 합이 n을 벗어나면 그 상담은 불가한 상담이다.

n을 벗어나지 않다면 (n번째 날 상담 비용 + (n + 상담이 지속되는 날)번째 상담 비용)의 합과, n+1번째 날의 상담 비용 중 더 큰 값을 구해주면 풀 수 있다.

code (Python)

n = int(input())
# 각 날의 (상담일수, 금액)
schedule = [list(map(int, input().split())) for _ in range(n)]
cost = [0] * (n+1)

for d in range(n-1, -1, -1):
    # 날이 넘어가서 상담을 할 수 없다면
    if d + schedule[d][0] > n:
        # 수익에는 변동 없음
        cost[d] = cost[d+1]
    # 상담을 할 수 있다면
    else:
        # max(현재 상담을 하고 끝난 후 다른 상담까지 했을 때 받는 금액, 다음 상담으로 받는 금액)
        cost[d] = max(schedule[d][1] + cost[d + schedule[d][0]], cost[d+1])

# 얻을 수 있는 최대 이익
print(max(cost))

self code review

나는 이 문제를 보고 바로 이건 DP다! 라고 생각했는데, 다른 분들의 풀이를 보니 Brute Force 방법의 풀이 과정도 보였다.

Brute Force 방법으로도 다시 풀어보려고 한다.