백준 11052(JAVA)

문제

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

풀이

민규는 N개의 카드를 사는데 최대 가격을 지불해야한다.

최초 시도할때 나의 생각은

1. N개의 카드를 산다하면 1개가든 팩 N개, 1개가 든 팩 N - 1개 + 2개가 든 팩 1개, 1개가든 팩 N - 2개 + 2개가 든 팩 2개, ... 이런식으로 경우의수를 모두 구해서 최대값을 구해야하나? 즉 브루트포스로 풀어야하나란 생각을 했다.

이렇게 생각하니 어떻게 풀어야할지도 모르겠고 막막했다.

그래서,
dp를 통해서 풀자! 라는 생각을 했다.

i개의 카드를 사기위해 최대 가격을 지불해야한다.
이미 dp테이블에 1부터 i - 1까지 카드를 살때 최대 가격이 적혀져있다고 가정하자.
그렇다면, i개를 사기 위해 따져봐야하는 경우는

1. dp[1] + dp[i - 1]
2. dp[2] + dp[i - 2]
3. dp[3] + dp[i - 3]
   ....

정말 간단해진걸 알수 있다.

이런 경우만 따져서 최대값을 갱신해 나가면 된다.

나는 최초에 dp테이블을 입력되는 가격으로 하였다.(참고!)

코드

package restudy_1.algostudy;

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

public class Main11052 {
    static int N;
    static int[] dp = new int[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i < N + 1; i++){
            dp[i] = Integer.parseInt(st.nextToken());
        }

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

        System.out.println(dp[N]);
    }
}