백준(baekjoon) [JAVA] - 11052번: 카드 구매하기

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

11052번: 카드 구매하기

---

import java.io.*;

// 카드 구매하기
public class _11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        String[] input = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(input[i - 1]);
        }

        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                ans[i] = Math.max(ans[i], ans[i - j] + arr[j]);
            }
        }
        bw.write(ans[n] + "");

        bw.flush();
        bw.close();
    }
}

---

MEMO

-- 카드 n개 구매값의 최댓값을 ans 배열에 저장하는 점이 핵심

-- ex) 5개의 카드값은 1개만 있는 카드를 살 때의값 + 4개의 카드가 들어간 것을 살 때의 최대값 or 2개의 카드가 들어간 것을 살 때의 카드값 + 3개의 카드가 들어간 것을 살 때의 카드값 ... 중 최댓값이 됨

 

!! 조금 어려웠던 dp 문제 !!