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

출처-https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

 

내 생각 :

n개의 카드를 산다고 한다면 i가 1부터 2/n까지 dp[n-i]+dp[i]와 기존의 dp[n]을 비교해서 가장 큰 값을 dp[n]에 넣어준다.
이렇게 1부터 n까지의 dp 배열을 순서대로 저장해주면 가장 큰 수를 찾을 수 있다.

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int dp[]=new int[n+1];
		for (int i=1;i<=n;i++)
			dp[i]=scan.nextInt();
		
		for (int i=2;i<=n;i++) {
			for (int j=0;j<=i/2;j++) {
				if (dp[i]<(dp[i-j]+dp[j]))
						dp[i]=dp[i-j]+dp[j];
			}
		}
		System.out.println(dp[n]);
	}

}