[알고리즘풀이 with python] 백준 14501번 - 퇴사

설명 퇴사일까지의 모든 기간에서 가장 많은 수익을 얻을 수 있는 상담들을 골라야한다. 입력으로는 상담 일정표의 일수 N과 각각의 상담 기간 t, 금액 p가 주어진다.

해당 문제를 DP(Dynamic Programming)로 풀이하기 위해서는 뒤에서부터 거꾸로 생각하는 것이 좋다. 우선 마지막 날부터 시작해서, 해당 날짜에 상담을 수행할 수 있는 경우와 수행할 수 없는 경우를 확인해가며 최대 수익을 저장하는 배열 dp를 채워나간다.

해당 날짜에 상담이 불가능한 경우, dp[i+1] 값을 그대로 가져온다. 해당 날짜에 상담이 가능한 경우, 두 값을 max를 사용하여 갱신한다.

코드는 다음과 같다. dp[i] = max(dp[i+1], p[i] + dp[i + t[i]]) 참고로 i는 날짜 변수다. ( 1일, 2일, 3일 ...) p[i] + dp[i + t[i]]라는 것은 i일에 상담한 경우 p[i]라는 보상을 받고 ( = p[i]) i + t[i]라는 것은 현재날짜 + 걸린시간이며, ...