[BOJ 16194] 카드 구매하기2(java)

Bottom-up 풀이

package basics_400;

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

public class BOJ16194 {
	//memo[n] = n개의 카드를 구매하기 위해 지불해야 하는 금액의 최소값 
	static int[] memo;
	//p[i] 카드팩 i개가 포함된 카드팩의 가격 
	static int[]p;
	static int cardPurchase(int n) {

		memo[0] = 0;
		//카드 갯수 1부터 n까지 
		for (int i = 1; i <= n; i++) {
			//최솟값을 구하기 위해 맨 처음 비교 대상은 큰 값으로 할당  
    		memo[i] = Integer.MAX_VALUE;
    		//ex )2개 카드 구매 최소값 구하는 경우
    		// 		memo[2] -> memo[2]와, memo[1]+p[1] (1개 최소값 + 1개 구입)
    		//				   memo[2]와, memo[0]+p[2] (2개짜리 카드2개 구입)
    		
            for (int j = 1; j <= i; j++) {
            	//비교해서 최솟값을 저장 
            	memo[i] = Math.min(memo[i], memo[i - j] + p[j]);
            }
        }
		
		return memo[n];
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		memo = new int[n+1];
		p = new int[n+1];
		st = new StringTokenizer(br.readLine()," ");

		//카드팩 값 넣어줌 
		for(int i=1;i<=n;i++) {
			p[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(cardPurchase(n));

		
	}

}