14501 - 퇴사

 

---

 

문제

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

14501번: 퇴사

 

풀이

해당 문제는 뒤에서부터 접근하여 최댓값을 갱신하는 방식으로 풀 수 있다.

 

D[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이라고 정한다.

 

이후 뒤에서부터 (지금 날짜 + 오늘 일하면 걸리는 날짜) <= n 일 경우

값을 갱신할지 말지 정해주면 된다.

 

만약 오늘 일하는게 여태 이익의 최댓값보다 작다면 갱신할 필요가 없고 (이 날 일을 할 필요가 없음), 크다면 갱신해준다.

 

 

코드

n = int(input())
d = [0] * (n+1)
t = []
p = []
max_value = 0

for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

# 뒤에서부터 탐색한다.
for i in range(n-1, -1, -1):
    limit = t[i] + i

    # 근무를 할 수 있다면
    if limit <= n:
        d[i] = max(p[i] + d[limit], max_value)
        max_value = d[i]
    else:
        d[i] = max_value
print(max_value)

 

후기

 

해당 문제를 푸는 방법은 다양한 거 같다. 앞에서부터 접근할 수 도 있고.. n이 작다보니 완전탐색으로도 충분히 풀 수 있다.

 

아이디어를 떠올리는 것과 구현은 항상 별개라고 생각한다. 아이디어를 명확하게 정리해서 구현으로 손쉽게 옮길 수 있도록 하는 연습이 더 필요할 거 같다.