[codeground] 31. 프리랜서

codeground - Practice - SCPC 2회 예선 - 31. 프리랜서
문제 : https://www.codeground.org/practice/practiceProblemList

---

DP를 Top-down(탑다운) 방식으로 채워나가면서 문제를 해결합니다.

D[0][ind] = ind주에 P사 작업했을 때 얻을 수 있는 최대 이익
D[1][ind] = ind주에 Q사 작업했을 때 얻을 수 있는 최대 이익
go(int ind) = ind주까지 작업했을 때 얻을 수 있는 최대 이익 반환

만약 ind주에 P사를 작업했을 때 얻을 수 있는 최대 이익은
D[0][ind] = go(ind-1) + P[ind] 입니다.
ind주에 Q사를 작업했다면 그 전주에도 Q사 작업을 해야 하므로
D[1][ind] = go(ind-2) + P[ind]가 됩니다.
Q사 작업은 2주가 소요되므로 첫째주 부분의 예외처리를 잘 처리해야 하는데 이 문제에서는 첫째 주에 요청한 작업은 Q사도 한 주 만에 할 수 있다고 했으므로 별다른 예외처리를 하지 않아도 됩니다.

정답은 D[0][n]과 D[1][n] 중 큰 수가 됩니다.

---

소스 코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/31.%20%ED%94%84%EB%A6%AC%EB%9E%9C%EC%84%9C.cpp

fpdjsns/Algorithm