[백준] 14501번: 퇴사 - Python

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

 

아이디어

• 최대가 될 수 있는 경우를 찾는 문제니 DP를 쓰면 되겠다.
• dp 배열엔 i번째까지 일했을 경우 얻을 수 있는 최대 수익이 저장된다.
• 2중 for문을 통해 i번째 일을 했을 경우 다음 할 수 있는 일에 대한 모든 dp 값을 구하고 최대값을 저장하는 방식으로 진행 하면 될 듯 하다.

 

구현

N = int(input())

li = [list(map(int, input().split())) for i in range(N)]

dp = [0 for i in range(N+1)]


for i in range(N):
    for j in range(i+li[i][0], N+1):
        if dp[j] < dp[i] + li[i][1]:
            dp[j] = dp[i] + li[i][1]

print(dp[-1])

 

마무리

bottom-up 방식으로 풀었지만 반대로 top-bottom도 가능 할 듯 하다. 

역으로 돌면서 이 일을 하면 가능한 일부터 dp 판단은 위와 같게 진행하면 된다.

간단한 dp문제로 쉽게 풀었다.