글 읽기 - 동적계획법으로 풀었는데 시간초과가 나네요....고수님의견 부탁합니다.

naegeora 7년 전 0

아래 로직으로 동적계획으로 풀었는데, 시간복잡도가 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);}

import java.util.Arrays;
import java.util.Scanner;

class work implements Comparable<work>{
	public long end,profit;
	public work(long a,long b){
		this.end=a;
		this.profit=b;
	}
	@Override
	public int compareTo(work o) {
		// TODO Auto-generated method stub
		return (int) (end-o.end);
	}
}


public class Main {

	static long[] D;
	static int N;
	static long answer;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		N=sc.nextInt();
		D=new long[N];
		work joblist[]=new work[N];
		for(int i=0;i<N;i++){
			long a=sc.nextLong();
			long b=sc.nextLong();
			joblist[i]=new work(a,b);
		}
		
		Arrays.sort(joblist);
		for(int i=0;i<N;i++){
			D[i]=joblist[i].profit;//초기화
		}
		
		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);
			}

		answer=-1;
        long maxVal = Long.MIN_VALUE;
        for (long val : D) {
            if (maxVal < val) {
                maxVal = val;
            }
        }
        answer=maxVal;
		System.out.println(answer);		
		sc.close();
	}

}

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

문제

문제

출처

ICPC

동적계획법으로 풀었는데 시간초과가 나네요....고수님의견 부탁합니다.

naegeora 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말