[백준(Baekjoon)][자바(java)] 7579 : 앱 / 동적 계획법 2

 

www.acmicpc.net/problem/7579

7579번: 앱

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ),
		    m = Integer.parseInt( st.nextToken() ), i, j;
		int b[] = new int[n], c[] = new int[n];  // memory(byte), cost
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ )
			b[i] = Integer.parseInt( st.nextToken() );
		st = new StringTokenizer( br.readLine() );
		int c_sum = 0;
		for( i = 0; i < n; i++ ) {
			c[i] = Integer.parseInt( st.nextToken() );
			c_sum += c[i];
		}
		br.close();
		
		int dp[] = new int[c_sum+1];	// i cost를 써서 확보할 수 있는 최대 메모리
		for( i = 0; i < n; i++ ) {
			for( j = c_sum; j >= c[i]; j-- ) {
				if( dp[j-c[i]] != 0 ) {
					if( dp[j] < ( dp[j-c[i]] + b[i] ) )
						dp[j] = ( dp[j-c[i]] + b[i] );
				}
			}
			if( dp[c[i]] < b[i] )
				dp[c[i]] = b[i];
		}
		
		for( i = 0; i <= c_sum; i++ ) {
			if( dp[i] >= m ) {
				System.out.println( i );
				break;
			}
		}
	}
}

( 코드 참고 : https://hoho325.tistory.com/165 )

 

*  동적 계획법

-  냅색 문제의 응용
-  원래의 냅색 문제라면 dp[i][j]는 i번째 요소까지 포함하여 무게의 합이 j가 되는 최대 가치를 의미하는 것이다.
-  이를 응용하여 dp[i]는 i 비용으로 비활성화 할 수 있는 최대 메모리가 되도록 한다.