[백준] 퇴사 14501

이번 문제는 퇴사이다.

https://www.acmicpc.net/problem/14501

생각보다 어려웠는데 그 이유는 아직 재귀함수를 잘 못다루는 것 같다ㅎㅎ

이런 문제는 문제를 풀기전에 어떻게 설계하느냐에 따라 달라지는 것 같다.

(사실 모든 문제가 그렇다 ㅎㅎ..)

재귀함수에 대한 문제를 조금 더 풀어봐야겠다.

우선 day와 pay를 나란히 입력받는다.

그 뒤 함수를 호출할 것인데 이 때 들어가는 인자는 sum과 idx이다.

idx가 입력받은 n과 같아지면 정상종료되야한다고 판단하며

문제에서 최대이익을 원했으니 sum과 ans중 최대값을 비교하여 ans에 저장한다.

n보다 idx보다 커질 경우 상담을 할 수 없는 것이기 때문에

이 경우에도 종료시키는 것이 맞다.

idx==n이 되지 않았다면 방금 상담한 날짜와 돈을 더해주고 다시 함수를

호출해야한다. 그러므로 sum에 상담을 통해 얻은 이익인 pay[idx]를 더해주고

해당 상담에 필요한 날짜만큼 idx에 pay[idx]를 더해줌으로써 idx를 건너뛰어야 한다.

상담에 필요한 날짜에 속하는 일 수의 다른 상담은 할 수 없기 때문이다.

만약 상담일 수가 더 너무 커서 퇴사해야할 날짜를 넘기게 되는 경우,

다음 상담을 기약해야하므로 그것보다 적은 상담일 수를 탐색해야한다.

이 경우에는 이득을 얻지 못했으니 sum에는 아무 값도 더해주지 않으며

idx는 다음 날에 있는 상담부터 살펴보게되기 때문에 1을 더해주면 된다.!!