[백준] 14501번 퇴사 ★

📌 [삼성 SW 역량 테스트 기출]

💡문제접근

• 코드로 구현하는 과정이 너무 힘들었다. 맨 뒤에서부터 가능한 경우를 확인하여 얻을 수 있는 최대 금액을 구했다.
• 테스트케이스에 나와있는 예제를 이용하자. 6, 7일차에 잡혀있는 상담의 소요 일수는 각각 4, 2일로 백준이는 8일차에 퇴사를 하기 때문에 상담을 할 수 없다. dp리스트에 0을 추가한 이유가 바로 이런 이유 때문이다.
• 4일차에 상담을 하고 5일차에 상담을 하면 이익을 얻을 수 있으므로 백준이가 일할 수 있는 시간 범위 내에서라면 dp리스트의 값을 비교해서 최댓값을 저장한다.

💡코드(메모리 : 30616KB, 시간 : 36ms)

N = int(input())
t = []
p = []
dp = []
for _ in range(N):
    T, P = map(int, input().split())
    t.append(T)
    p.append(P)
    dp.append(P)

dp.append(0)
for i in range(N-1, -1, -1):
	# N+1일차가 되면 백준이는 일할 수 없기 때문에 조건문으로 걸러야 한다.
    if i + t[i] > N:
        dp[i] = dp[i+1]
    # 만약 백준이가 일할 수 있는 시간 범위내라면?
    else:
        dp[i] = max(dp[i+1], dp[i+t[i]] + p[i])
print(dp[0])

💡소요시간 : 2h