[백준] 7579 앱

문제링크: www.acmicpc.net/problem/7579

7579번: 앱

1년 전에 풀다가 실패했던 문제다. 다시 풀려고 했는데 나아진 게 없는지 잘 풀리지 않았다. 반성했다.

그때 답을 보고도, 제대로 이해하지 않고 넘어갔던 것 같다. 이번 기회에 차근차근 이해 해보려 했다.

또, 재귀 호출을 통한 메모이제이션 방법이 떠오르지 않아서 bottom-up 방식으로 풀었지만 검색해보니까 재귀로 해결한 코드가 있었다. bottom-up을 어려워 하는 내겐 좋은 공부가 됐다. 다음번엔 top-down 방법으로 같은 문제를 풀어봐야겠다.

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

public class Main {
	public static int N,M;
	public static int []memory;
	public static int []cost;
	public static int [][]dp;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		memory = new int[N+1];
		cost = new int[N+1];
		dp = new int[N+1][10001];
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++){
			memory[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++){
			cost[i] = Integer.parseInt(st.nextToken());
		}
		int ans = 987654321;
		exit:for(int i=1;i<=N;i++){
			for(int j=0;j<=10000;j++){
				if(j-cost[i] >=0)
					dp[i][j] = Math.max(dp[i-1][j-cost[i]] + memory[i],dp[i-1][j]);
				else
					dp[i][j] = dp[i-1][j];
				if(dp[i][j]>=M){
					ans = Math.min(ans, j);
				}
			}
			
		}
		System.out.println(ans);
	}

}