글 읽기 - DP 질문이요.

do01124 7년 전 0

포도주 시식 문제를 Top-Down 방식으로 풀었습니다.

문제는 잘풀렸지만, 채점시간이 920 MS 걸렸습니다.

혹시 Top-Down으로 훨씬 효율적인 코드를 작성할 수 있을까요?

class P02156 {
	
	int[] arr;
	int[][] cache;
	
	public int solve(int[] arr) {
		
		this.arr = arr;
		this.cache = new int[arr.length+1][4];
		for(int i=0; i<cache.length; i++)
			Arrays.fill(cache[i], -1);
		
		int answer = Math.max(dp(0, 1), dp(1, 1));
		return answer;
	}
	
	private int dp(int idx, int step) {
		
		if(idx >= arr.length || step >= 3)
			return 0;

		if(cache[idx][step] != -1)
			return cache[idx][step];
		
		int ret = dp(idx+1, step+1) + arr[idx];
		for(int i=idx+2; i<arr.length; i++) {
			ret = Math.max(ret, dp(i, 1) + arr[idx]);
		}

		cache[idx][step] = ret;
		return ret;
	}
}

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

문제

문제

출처

ICPC

DP 질문이요.

do01124 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말