[백준] 14501번: 퇴사 - python

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

14501번: 퇴사

 

배울게 참 많은 문제

 

첫번째 아이디어

DFS를 이용하여 상태트리를 생성하여 계산하는 방식과

N = int(input())

def DFS(L, sum):
    global res
    if L == N+1:
        if res < sum:
            res = sum
    else:
        if L+day[L] <= N+1:
            DFS(L+day[L], sum+profit[L])
        DFS(L+1, sum)



day = [0]
profit = [0]
for i in range(N):
    a, b = map(int, input().split())
    day.append(a)
    profit.append(b)

res = -27600000
DFS(1,0)
print(res)

 

 

두번째는 DP를 이용하여 최대값을 계속 저장해나가는 방식이다.

 

n = int(input())
schedule = []
dp = [0] * (n+1)
for i in range(1,n+1):
    a, b = map(int, input().split())
    schedule.append([a,b])

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

print(dp[-1])

 

완성

 

두가지 방식 다 해보면 좋을 것 같다.