[백준알고리즘] 14501번: 퇴사 -Python

[백준알고리즘] 14501번: 퇴사 -Python

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

14501번: 퇴사

퇴사하기 전까지 가장 많은 돈을 벌 수 있도록 해야 한다.

 

며칠에 걸리는 상담인지에 따라 며칠간 상담을 추가로 할 수 없을 수도 있다.

 

나는 dp처럼 문제를 풀었다. 1일 차부터 순서대로 선택을 하면서 각 날짜의 일을 했을 때 최대로 벌 수 있는 금액을 유지한다. 그리고 이 최대로 벌 수 있는 금액에 다음에 할 수 있는 일 들의 금액을 더하면서 유지한다. 음... 코드를 보는 게 설명보다 쉬워 보인다...

 

배열로 비교를 해보도록 하자. 처음의 값은 다음과 같다.

data = [(3, 10), (5, 20), (1, 10), (1, 20), (2, 15), (4, 40), (2, 200)] 가 주어졌을 때 charge의 값은 다음과 같다.

 

charge = [10, 20, 10, 20, 15, 40, 200]

이는 각 날에 해당 일을 했을 때의 얻을 수 있는 금액이다.

 

여기서 1일의 일을 한다고 했을 때 걸리는 기간은 3일이다. 따라서 charge[3]부터 다른 일을 추가로 할 수 있다. 여기서 charge의 값들은 charge[1] + data[i][1] > charge[i] 일 경우에는 charge의 값을 변경시켜준다. 그날의 일만 하는 것이 아니라 1일의 일도 추가로 하면 더 많이 벌 수 있기 때문이다.

 

마찬가지의 일들을 해주고, 기간 때문에 할 수 없는 일을 없애주면 벌 수 있는 최대 금액을 구할 수 있다.

 

n = int(input())
data = [tuple(map(int, input().split())) for _ in range(n)]
charge = list(map(lambda x: x[1], data))

for i in range(n):
    if i + data[i][0] > n:
        charge[i] = 0
        continue
    
    t = charge[i]
    for j in range(i + data[i][0], n):
        if t + data[j][1] > charge[j]:
            charge[j] = t + data[j][1]

print(max(charge))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다