[백준 14501] 퇴사 [C]

백준 14501 - 문제

백준 14501 - 입/출력

---

풀이

각 요일마다 주어진 상담을 진행할 경우 겹치는 분기를 표시한 그림이다.

상담 시작요일은 다 다르지만, 상담이 끝나는 날은 다른 상담기간과 겹치는 것을 확인할 수 있다.

때문에, brute force방식(또는 bottom-up)으로 풀이할 경우 모든 상담일정 기간 이후의 모든 기간에 대해 반복문을 돌며 최대 수익을 반영해줘야 한다.

 

아래 그림처럼 말이다.

좀 더 효율적으로 풀이해보자.

이전 방법은 현재 상담을 통해 미래의 최대 수익이 변화한다는 특징이 있었다.

하지만, 미래에서 현재까지 거꾸로 최대 수익을 계산하는 방법은 어떨까?  

미래의 상담일정은 현재의 상담일정에 대해 영향을 끼치지 않는다. 시간은 거꾸로 흐르지 않기 때문이다!

상담 일정이 퇴사 일정을 초과하지 않는다면, 다음 날(day + 1)에 상담해서 얻는 최대 수익( dp[ day + 1 ] )과 이번에 진행할 상담( P[ day] ) 그리고 상담이 끝난 후 진행할 수 있는 상담들의 최대 수익( dp[ day + t ] )중 더 큰 수익을 누적시키자.

 

---

소스코드

소스코드 보기

---

출처

14501번: 퇴사