[BAEKJOON] 11052. 카드 구매하기

acmicpc

[BAEKJOON] 11052. 카드 구매하기

코드와이 2021. 4. 15. 15:55

DP

문제링크

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

package acmicpc.Silver1;

import java.util.Scanner;

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();
		}
		
		for(int i = 1 ; i <= n ; i++) {
			for(int j = 1 ; j <= i ; j++) {
				arr[i] = Math.max(arr[i], arr[i-j] + arr[j]);
			}
		}
		System.out.println(arr[n]);
		sc.close();
	}
}