[백준] 11052번 - 카드 구매하기

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

11052번: 카드 구매하기

---

풀이과정

 

dp[n] : n개의 카드를 구매하는 가격의 최대값

arr[n] : n개의 카드가 들어있는 카드팩의 가격

 

[예시]

dp[1] = arr[1]

 

dp[2] = dp[1] + arr[1]

dp[2] = arr[2]

 

dp[3] = dp[2] + arr[1]

dp[3] = dp[1] + arr[2]

dp[3] = arr[3]

 

...

 

이런식으로 가능한 경우의 수가 나오는데, 우리는 최댓값을 구해야하므로 위의 과정 중 최댓값을 dp 배열에 계속 저장해주면 된다!

 

점화식은? 일반항 구하기!

 

---

 

[자바코드]

import java.util.Scanner;

public class boj11052 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1;i<=n;i++) {
            arr[i] = scanner.nextInt();
        }

        dp[0] = 0;
        dp[1] = arr[1];

        for(int i=1;i<=n;i++) {
            for(int j=1;j<=i;j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + arr[j]);
            }
        }

        System.out.println(dp[n]);

    }
}