편집 시간: 2022년 4월 21일 오후 7:59
코드
Algorithm/14501.py at main · Junroot/Algorithm
풀이
인풋 범위를 보니 브루트포스로 구현해도 되지만, dp를 이용해서 풀었다.
- f(x): x일까지의 최대 이익
- f(x) = max(consults[index][2] + f(consults[x][1] - 1), f(x-1))
- consults[index][1] == x인 경우만
다른 풀이
다른 사람의 풀이를 보니 상담 완료날짜 기준이 아니라 시작날짜를 기준으로 dp로 풀면 정렬을 할 필요가 없었다.
O(nlogn)을 O(n)문제로 해결할 수 있다.