카드 구매하기

📍 문제 설명

 

💡 접근

최대 금액을 담을 배열 dp[n]이 필요하다.

점화식을 세워야하는데.

dp[4] 부터 보자면

1장 + 3장 가격

2장 + 2장 가격

3장 + 1장 가격

4장 + 0장 가격의 최댓값을 뽑아내면 된다.

따라서 점화식은 dp[i] = Math.max(dp[i], dp[i-j] + dp[j]); 로 사용할 수 있다.

타 블로그를 참고해보니 dp[j]가 아닌 arr[j]의 값을 넣었는데

금액 n까지의 최대 금액 구하는 문제라서 둘이 비슷한 의미로 사용할 수 있겠다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static int[] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            arr[i] = kb.nextInt();
            dp[i] = arr[i];
        }
        //카드 최댓값 담을 배열

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

    }

    private void solution() {
        //1, 5, 6, 7원
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + dp[j]);
            }
        }
    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static int[] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            arr[i] = kb.nextInt();
            dp[i] = arr[i];
        }
        //카드 최댓값 담을 배열

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

    }

    private void solution() {
        //1, 5, 6, 7원
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i-j] + dp[j]);
            }
        }
    }

}