글 읽기 - 동전2 질문입니다! (재귀호출 사용)

tnals 8년 전 0

메모이제이션을 활용한 재귀적 동적계획법으로 작성해봤습니다.

minimize(int capacity, int item)에서

item은 현재 몇 번째 동전의 개수를 결정하는지를 나타내고

capacity는 앞으로 채워야할 남은 가치의 합을 나타냅니다

오류가 있는 부분이 어디일까요?ㅠㅠ

package baekjoon;

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

public class Coin2 {
	public static int n;//동전 종류
	public static int k;//가치의 합
	public static int[] c;//동전의 가치
	
	public static int[][] cache;//메모이제이션
	
	public static int INF=10000;
	
	public static int minimize(int capacity, int item)
	{
		if(item==n)
		{
			if(capacity==0)
				return 0;
			else
				return INF;
		}
		
		if(cache[capacity][item]!=-1) return cache[capacity][item];
		
		int result=INF;
		
		for(int i=0; i<=capacity/c[item]; i++)
		{
			result=Math.min(result, i+minimize(capacity-c[item]*i,item+1));
		}
		
		return cache[capacity][item]=result;
	}
	public static void main(String[] args) throws Exception {
		
		Scanner sc = new Scanner(new FileInputStream("bj_coin2.txt"));
		
		n=sc.nextInt();
		k=sc.nextInt();
		
		c=new int[n];
		for(int i=0; i<n; i++)
			c[i]=sc.nextInt();
		
		cache=new int[k+1][n];
		for(int i=0; i<=k; i++)
			for(int j=0; j<n; j++)
				cache[i][j]=-1;
		
		int result=minimize(k,0);
		if(result>INF)
			System.out.println(-1);
		else
			System.out.println(result);
	}

}

baekjoon 8년 전 1

ㅇㅣ거 틀리나요?

제가 package 지우고, 클래스 이름 Main으로 바꾸고, Scanner System.in 사용하게 바꾸니 맞았습니다를 받았습니다!

tnals 8년 전 0

아아! 제가 제출하는 코드상에서 지우지 않았던 부분이 있네요ㅠㅠ

더 자세히 봤어야 했는데ㅠㅠ답변 감사합니다:)

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

문제

문제

출처

ICPC

동전2 질문입니다! (재귀호출 사용)

tnals 8년 전 0

baekjoon 8년 전 1

tnals 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말