글 읽기 - 아..ㅠㅠ 왜 틀렸는지 모르겠어요 ㅠㅠ 도와주세요

woong611 6년 전 0

dp[][]를 각각 출력보면 결과값이 제대로 나오는거 같은데

안되는 경우를 못찾겠어요 ㅠㅠ 도와주세요

import java.util.*;

public class Main {

	
	public static int N;
	public static int K;
	public static int dp[][] = new int[101][10001];
	public static ArrayList<Integer> al = new ArrayList<Integer>();
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int temp;
		int _min = 100001;
		N = sc.nextInt();
		K = sc.nextInt();
		
		
		al.add(-1); //그냥 index 1부터 하고 싶어서
		
		for(int i = 1; i<=N; i++)
		{
			temp = sc.nextInt();
			al.add(temp);	
		}
			
		Collections.sort(al);
		
		for(int j =0; j<=K; j++)
		{
			dp[0][j] = 0;
		}
		
		for(int i =0; i<=N ; i++)
		{
			dp[i][0] = 0;
		}
		
		
		int q;
		for(int i =1; i<=N; i++)
		{
			for(int j = 1; j<=K; j++)
			{
				q = j/al.get(i);
				
				if(q == 0)
				{
					dp[i][j] = dp[i-1][j];
				}
				else if(q > 0 && dp[i-1][j - q*al.get(i)] + q*al.get(i) == j)
				{
					dp[i][j] = q + dp[i-1][j- q*al.get(i)];
				}
			}
			
			if(_min > dp[i][K] && dp[i][K] != 0)
			{
				_min = dp[i][K];
			}
			
			
		}
		
		
		if(_min != 100001)
		{
			System.out.println(_min);	
		}
		else
		{
			System.out.println(-1);
		}
		
		
		 
	}

}

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

문제

문제

출처

ICPC

아..ㅠㅠ 왜 틀렸는지 모르겠어요 ㅠㅠ 도와주세요

woong611 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말