naegeora   5달 전

아래 로직으로 동적계획으로 풀었는데, 시간복잡도가 O(N^2) 라서 시간초과가 나는데요...

혹시 다른방법이 있나요? 이게 최선인거 같은데....

로직:

1, end 기준으로 오름차순 정렬 되는 work class 생성.

2. 아래 동적계획 부분:  

for(int i=1;i<N;i++)
for(int j=0;j<i;j++){
if(joblist[j].end<joblist[i].end&&joblist[i].profit + D[j]>D[i])
D[i]=Math.max(D[i], D[j]+joblist[i].profit);}


댓글을 작성하려면 로그인해야 합니다.