Problem Solving
codeground : 프리랜서 [SCPC 2016 - 2차 예선]
1ssrek
2016. 10. 12. 10:28
codeground : 프리랜서 [SCPC 2016 - 2차 예선]
https://www.codeground.org/practice/practiceProbView.do?probId=31
간단한 DP로 해결할 수 있다.
일하는 데 일주일이 걸리는 P사의 각 주당 금액 을 Pi, 이주일이 걸리는 Q사의 각 주당 금액을 Qi라 하고, i번째 주에 받을 수 있는 가장 큰 금액을 Ai라 한다면,
Ai = max(Ai-1+ Pi, Ai-2 + Qi)
위와같은 단 하나의 점화식으로 DP를 구성하면 가뿐하게 AC를 받을 수 있다.