블로그 이사 중입니다 >> gumgood.github.io

14501 퇴사 본문

Problem Solving/문제 풀이

14501 퇴사

gumgood 2018. 11. 7. 12:43

C++11


dp[i] = (i일에 받을 수 있는 최대 수익)


i일에는 세 경우가 있다.


1) i일에 상담 중인 경우


2) i일에 상담이 끝나는 경우


3) i일에 상담을 하지 않는 경우



1), 3)의 경우 i일에 얻는 금액은 없다. 따라서 i-1일에 얻는 금액과 동일하다. 이를 점화식으로 나타내면

 

 dp[i] = dp[i-1]


2)의 경우 i일에 끝나는 상담에 맞는 금액을 더 얻는다.


 dp[i] = dp[j-1] + p[j];  여기서 j는 i일에 끝나는 상담의 시작일

 (구현은 dp[i]에서 dp[i + t[i] -1]로 값을 update시켜주는 방법을 썼다)

'Problem Solving > 문제 풀이' 카테고리의 다른 글

2162 선분 그룹  (0) 2018.11.07
6497 전력난  (0) 2018.11.07
14501 퇴사  (0) 2018.11.07
5363 요다  (0) 2018.11.07
5636 소수 부분 문자열  (0) 2018.11.07
14568 2017 연세대학교 프로그래밍 경시대회  (0) 2018.11.07
Tag
0 Comments
댓글쓰기 폼