백준 11052번 - 카드 구매하기 (Java 8)

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

16194번: 카드 구매하기 2

코드 :

1. dp, 바텀업

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

public class Main {
    static int[] dp;
    static int[] costArr;

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

        dp = new int[N + 1];
        costArr = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        dp[0] = 0;
        for (int i = 1; i < N + 1; i++) {
            costArr[i] = Integer.parseInt(st.nextToken());
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + costArr[j]);
            }
        }
        System.out.println(dp[N]);
    }

}

 

2.dp, 바텀업

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

public class Main {
    static int[] dp;
    static int[] costArr;

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

        dp = new int[N + 1];
        costArr = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i < N + 1; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
            for (int j = 1; j <= i/2; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + dp[j]);
            }
        }
        System.out.println(dp[N]);
    }

}

3. dp, 탑다운

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

public class Main {
    static int[] dp;
    static int[] costArr;

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

        dp = new int[N + 1];
        costArr = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i < N + 1; i++) {
            costArr[i] = Integer.parseInt(st.nextToken());
        }
        dp[1] = costArr[1];
        System.out.println(dp(N));
    }
    public  static int dp(int N){
            if(dp[N] > 0) return dp[N];

            /*틀린코드
            for (int i = 1; i <N+1 ; i++) {
                        dp[N] = Math.max(costArr[N], dp(N - i) + costArr[i]);
                    }
            return dp[N];
            */
            
            dp[N] = costArr[N];
            for (int i = 1; i <N+1 ; i++) {
                dp[N] = Math.max(dp[N], dp(N - i) + costArr[i]);
            }
        return dp[N];
    }
}

참고 :

https://broship.tistory.com/220 2번 코드를 여기서 참고했다. 카드 가격을 저장하는 배열을 만들지 않고, i를 2로 나누는게 이해가 안갔는데, 직접써보니 이해가 갔다.

https://hongjw1938.tistory.com/52 3번 코드는 여기서 참고했다. 왜 계속 값이 틀리나 했는데 갱신된 dp값이 서로 비교가 되지 않아서  였다. 이전 코드를 자세히 보면 갱신된 dp[N]값이 같이 비교되지 않고, 값을 담기만 한다. 첫 dp[N]값에 가격을 미리 넣어주고 dp[N]을 max메드 안에 넣어서 해결했다.

 

스스로 못푸는 문제가 많아 찝찝하다.