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

점화식은 빨리 세웠지만,, 구현하는게 어려웠다 ㅠ

Bottom-up 풀이

package basics_400;

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

public class BOJ11052 {
	//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++) {
			// j는 1부터 i와 같아질때까지 반복하면서
			// 최댓값을 찾는다. 
			//ex) memo[2] = 기존에 구한 memo[2](구한게 없다면 0)
			// memo[1]+p[1] = 1개 카드 구매~ 금액 최대 + 1개 들어있는 카드팩구입 가격 = 총 2개 사는거
			// 두개를 비교해서 더 큰 값을 넣어준다.
            for (int j = 1; j <= i; j++) {
                memo[i] = Math.max(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));

		
	}

}