백준 11052번 카드 구매하기(JAVA, DP)

<풀이방식>

각각 갯수로 카드를 살때의 가격이 담긴 card[]를 선언한다.
5개를 살때의 최대값은
4개 구매 최대값 + 1개 구매값
3개 구매 최대값 + 2개 구매 최대값
2개 구매 최대값 + 3개 구매 최대값
1개 구매 최대값 + 4개 구매 최대값
이 4가지의 경우 중 최대값을 가진다.

이를 위해 이중 포문을 돌면서
dp[i] = dp[i-j] + card[j];
이상태에서 그 이전 저장된 dp[i]와 비교해도 최대값이어야하므로
dp[i] = Math.max(dp[i], dp[i-j] + card[j]);

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		int [] card = new int [num+1];
		int [] dp = new int [num+1];
		
		//카드 배열 담기
		for(int i = 1 ; i < num+1 ; i++) {
			card[i] = sc.nextInt();
		}
		
		//초기값
		dp[1] = card[1] ;
		
		/*
		 * 예를 들면 5개를 뽑는 dp[5]는 4개뽑기 + 1개뽑기 , 3개뽑기 + 2개뽑기 ....
		 *  이거의 모두 최대값인 애를 뽑아야함
		 *  그래서 2중포문돌아야되고 포문 안쪽에서 계속 돌면서 이미 저장된 dp[i]값이랑도 
		 *  계속 비교하면서 max값을 찾아야됨
		 */
		for(int i = 1 ; i < num+1; i++){
			for(int j = 1 ; j <= i ; j++) {
				//안쪽 for문돌면서 그 이전에 저장된 값이랑도 비교해서 최대값이 되야해서
				//dp[i]와의 max 를 비교해줘야됨
				dp[i] = Math.max(dp[i], dp[i-j] + card[j]);
			}
		}
		
		System.out.println(dp[num]);
	}
}