카드팩 가격 정보를 담을 deck이라는 것과
i장을 구매했을때의 최대 가격을 담을 dp[i] 배열을 만들다
그래서 dp[4] 라는 것은 4장의 카드를 구매했을때의 최대 가격이다.
점화식을 세우기 위해서
귀류법으로 접근했다.
dp[1] = deck[1] 밖에 나오지 않는다.
dp[2] = deck[2] 와 deck[1]+deck[1] 중에서의 최대값이다.3부터는 이전값들 활용할수 있게 되는데 deck[3] 자체와 2장의 카드팩을 구매했을때의 최대 가격과 카드 1장의 가격을 더한것끼리 비교하게 되면
dp[3] = deck[3] 과 dp[2]+deck[1] 이다.조금 애매해서 4도 해보았다.
dp[4] 는 deck[4]와 dp[3]+deck[1]에다가 dp[2]+dp[2]가 추가로 있다.
(dp[1]=deck[1] 이다)
따라서 dp[4] = Math.max(deck[4],dp[3]+dp[1],dp[2]+dp[2])중에서 제일 큰값이다. dp[1]+dp[3]도 가능은 하겠지만 dp[3]+dp[1]과 같으므로 제외2중 for문을 이용하여
i를 돌때는 dp[i] = deck[i]를 해주고
j에서 각 경우중에서 제일 큰값을 dp[i]로 해서 비교해준다.for (int i = 2; i <= n; i++) { dp[i] = deck[i]; for (int j = 1; j < i; j++) { dp[i] = Math.max(dp[j] + dp[i - j], dp[i]); } }
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] deck = new int[n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
deck[i] = sc.nextInt();
}
dp[0] = 0;
dp[1] = deck[1];
for (int i = 2; i <= n; i++) {
dp[i] = deck[i];
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[j] + dp[i - j], dp[i]);
}
}
System.out.println(dp[n]);
}
}