글 읽기 - 어디가 잘못되었는지 모르겠습니다..

ljs921026 5년 전 1

knapsack으로 풀어봤습니다.

블록들을 하나씩 돌아가며

그냥 넘어가는경우,

left에 쌓는 경우,

right에 쌓는 경우,

로 나누어 dp를 적용했는데요,

메모리초과가 뜨는데 이유를 모르겠습니다.ㅠ

import java.util.*;

public class Main {
	static int n;
	static int[] block;
	static int sum;
	static int[][] cache;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		block=new int[n];
		sum=0;
		for(int i=0;i<n;i++) {
			block[i]=sc.nextInt();
			sum+=block[i];
		}
		cache=new int[n+1][sum+1];
		for(int i=0;i<=n;i++) {
			Arrays.fill(cache[i], -1);
		}
		System.out.println(tower(0,0));
	}
	
	public static int tower(int now,int diff) {
		if(now==n&&diff!=0)
			return Integer.MIN_VALUE;
		if(now==n&&diff==0)
			return 0;
		
		if(cache[now][diff]!=-1)
			return cache[now][diff];
		
		//기준은 더 낮은 탑의 높이로 해야 함.
		cache[now][diff]=0;
		cache[now][diff]=Math.max(cache[now][diff],tower(now+1,diff));//블록 안썼을 때
		cache[now][diff]=Math.max(cache[now][diff], tower(now+1,diff+block[now]));//높은 곳에 쌓았을 때
		if(block[now]>diff) //diff보다 큰 블록을 낮은 곳에 쌓을 때
			cache[now][diff]=Math.max(cache[now][diff], tower(now+1,block[now]-diff)+diff);
		else	//diff보다 작거나 같은 블록을 낮은 곳에 쌓을 때
			cache[now][diff]=Math.max(cache[now][diff], tower(now+1,diff-block[now])+block[now]);
		
		return cache[now][diff];

	}
}

ljs921026 5년 전 0

아 예외처리를 안했엇네요..

해결했습니다.

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

문제

문제

출처

ICPC

어디가 잘못되었는지 모르겠습니다..

ljs921026 5년 전 1

ljs921026 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말