글 읽기 - 메모리 초과... (java)

qls0860 4년 전 0

냅색 문제랑 퇴사 문제랑 유형이 똑같은 거 같은데

이차원 배열로 하는 게 아닌가요?

왜 메모리 초과가 나는 거죠?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int n, m, a[], c[], memo[][], MAX = 987654321;
	
    // nth 번째에서 memory만큼 메모리를 구했을 때 최소 비용
	static int min(int nth, int memory) {
		if (memory >= m) return 0; // 기저
		
		if (nth == n) return MAX; // 기저
		
		if (memo[nth][memory] != -1) return memo[nth][memory]; // 메모
		
        // 활성화 안할 때 vs 활성화 할 때
		return memo[nth][memory]= Math.min(min(nth + 1, memory), c[nth] + min(nth + 1, memory + a[nth]));
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" "), x = br.readLine().split(" "), y = br.readLine().split(" ");
		
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		
		a = new int[n];
		c = new int[n];
		memo = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(x[i]);
			c[i] = Integer.parseInt(y[i]);
			Arrays.fill(memo[i], -1);
		}
		
		bw.write(min(0, 0) + "");
		bw.close();
	}
}