CEO

문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 기존에 풀었던 퇴사 문제에서 N의 범위가 커진 문제이다. N의 범위가 커짐에 따라 DFS로 풀지 않고 DP로 풀어야 문제를 해결할 수 있다. 즉 최대 수익을 완전 탐색을 통해 찾지 않고, 메모이제이션을 통해 값을 누적시켜가며 N일 까지 진행시켜야 한다. 점화식은 현재 날짜 + 일하는데 필요한 날짜