[BOJ 7579번] 앱(JAVA)

www.acmicpc.net/problem/7579

7579번: 앱

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N, M;
	static int[] m, c;
	static int answer=Integer.MAX_VALUE;
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		N=Integer.parseInt(s[0]);
		M=Integer.parseInt(s[1]);
		m=new int[N];
		c=new int[N];
		String s1[]=br.readLine().split(" ");
		String s2[]=br.readLine().split(" ");
		for(int i=0;i<N;i++) {
			m[i]=Integer.parseInt(s1[i]);
			c[i]=Integer.parseInt(s2[i]);
		}
		int dp[][]=new int[N][100001];
		for(int i=0;i<N;i++) {
			int cost=c[i];
			int memory=m[i];
			for(int j=0;j<=10000;j++) {
				if(i==0) {
					if(j>=cost)	dp[i][j]=memory;
				}
				else {
					if(j>=cost)	dp[i][j]=Math.max(dp[i-1][j-cost]+memory, dp[i-1][j]);
					else dp[i][j]=dp[i-1][j];
				}
				if(dp[i][j]>=M) answer=Math.min(answer, j);		
			}
		}
		System.out.println(answer);
	}
}

아래 블로그 링크를 참고하여 문제를 풀어보았습니다.

dragon-h.tistory.com/9

[백준 7579 : JAVA] 앱 / Dynamic Programming