카드구매하기

• 풀이시간 약 2시간 (생각을 오래했다.)
• tmp배열에 각 카드수로 구매할 수 있는 금액의 최대값을 저장하고 최대값 배열을 돌면서 더해나간다.

public class 카드구매하기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N + 1];
		for (int i = 1; i <= N; i++)
			arr[i] = sc.nextInt();

		////////////////////////////////////
		int[] tmp = new int[N + 1];
		tmp[1] = arr[1];
		for (int i = 2; i <= N; i++) {
			int max = 0;
			for (int j = 1; j <= i / 2; j++) {
				max = Math.max(max, arr[j] + tmp[i - j]);
			}
			max = Math.max(max, arr[i]);
			tmp[i] = max;
		}
		//////////
		
		System.out.println(tmp[N]);
	}
}