[BOJ] 14501 : 퇴사 (15486 : 퇴사2)

출처 : https://www.acmicpc.net/problem/14501
           https://www.acmicpc.net/problem/15486


퇴사 문제는 퇴사2문제와 구성은 같으나 N의 범위가 15와 1500000의 차이가 있는 문제이다.
퇴사 문제는 완전탐색으로도 풀 수 있으나 문제의 구성을 보면 DP로 풀 수 있다.

문제의 점화식은 매우 간단한데, 현재 날짜를 i, 상담할 때의 비용을 cost라 하면 아래와 같이 표현할 수 있다.
D[i+day] = max(D[i+day],D[i]+cost)


소스 코드 : https://github.com/younghk/Problem_Solving/blob/master/BOJ/boj_14501.cpp