글 읽기 - 36% 지점에서 메모리 초과가 발생합니다.

yoodly 5년 전 0

아래 소스에서 메모리 초과가 발생하는데 이유를 모르겠습니다.

문제의 메모리 제한이 그렇게 박하지 않는데, 뭐 떄문에 그럴까요?

조언 부탁드립니다~

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		int N, K;
		int[] coin, dp;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		coin = new int[N];
		dp = new int[K+1]; 	
		for (int i = 0; i < N; i++) coin[i] = Integer.parseInt(br.readLine());
		br.close();
		
		for (int i = 0; i <= K; i++) dp[i] = i;  // 초기 최대 값은 자기의 금액으로 한다.
		
		for (int i = 0; i < N; i++) {  // coin 기준으로 가장 작은 수부터 시작.
			for (int j = coin[i]; j <= K; j++) {  // J를 동전의 가치로 나눈 수와 기존 값 중에서 작은 수를 넣는다.
				dp[j] = Math.min(dp[j], j/coin[i] + dp[j%coin[i]]); // 내가 생각한 풀이
//				dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);       // 다른 사람이 생각한 풀이
			}
		}
		System.out.println(dp[K]);
	}
}

yoodly 5년 전 0

동전교환을 DP 공부하면서 배열로 풀었더니 heap size 에러나는 것이었네요. 다른 방식으로 풀어서 해결했습니다. ^^;;;

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

문제

문제

출처

ICPC

36% 지점에서 메모리 초과가 발생합니다.

yoodly 5년 전 0

yoodly 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말