[백준] 14501 퇴사

백준 14501번 퇴사

다이나믹 프로그래밍 / 브루트포스

 

 

[문제]

 

 

실버3문제였지만 다이나믹이 개인적으로 꽤 까다로운 것 같다.

이 부분에서 핵심이 되는 부분은 상담 시간이 n을 초과하는지 비교하는 부분과 금액(p)값의 최댓값이 되도록 갱신하는 부분이다.

 

 

 

[과정]

 

우선 거리비교를 위해서 역순으로 비교를 해야한다.

dp라는 새로운 1차원 배열을 생성하여 역순으로 진행했을 때 dp[i]에 금액의 최댓값이 저장된다.

 

• 1차원 배열(dp)를 n만큼 거리0으로 초기화
• 역순으로 반복문 진행
• dp[i]에 '현재 위치의 금액 + 현재 필요한 시간을 뺀 dp[i]의 값'과 이전의 dp[i]값 중 최솟값을 저장
• dp의 첫번째 원소를 출력

 

 

 

[소스코드]

 

# 퇴사

n = int(input())
data = []
for i in range(n):
    t,p = map(int, input().split())
    data.append([t,p])

dp = [0 for i in range(n+1)]
for i in range(n-1, -1, -1):
    if data[i][0] + i <= n:
        dp[i] = max(data[i][1] + dp[i + data[i][0]], dp[i+1])
    else:
        dp[i] = dp[i+1]

print(dp[0])

 

---

 

[통과]