[백준](Java) 11052 - 카드 구매하기

문제 링크

https://www.acmicpc.net/problem/11052

문제 풀이

카드팩 가격 정보를 담을 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]);
    }
}