[백준][11052번] 카드구매하기 1,2

문제 URL

• 카드구매하기 #1 https://www.acmicpc.net/problem/11052
• 카드구매하기 #2 https://www.acmicpc.net/problem/16194

나의 풀이 (카드구매하기 #1)

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static int[] d;
    public static int[] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer str = new StringTokenizer(br.readLine());
        cost = new int[n+1];
        d = new int[n+1];

        for(int i=1; i<=n; i++){
            cost[i] = Integer.parseInt(str.nextToken());
            for(int j=1; j<=i; j++){
                d[i] = Math.max(d[i], d[i-j] + cost[j]);
            }
        }

        System.out.println(d[n]);
    }
}

나의 풀이 (카드구매하기 #2)

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static int[] d;
    public static int[] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer str = new StringTokenizer(br.readLine());
        cost = new int[n+1];
        d = new int[n+1];

        for(int i=0; i<=n; i++)
            d[i] = -1;

        d[0] = 0;
        for(int i=1; i<=n; i++){
            cost[i] = Integer.parseInt(str.nextToken());
            for(int j=1; j<=i; j++){
              if(d[i] == -1 || d[i] > d[i-j]+cost[j])
                d[i] = d[i-j] + cost[j];
            }
        }

        System.out.println(d[n]);
    }
}

느낀점

동적계획법 을 이용한 문제다. 시간복잡도 : N*O(N) = O(N2)

점화식은 D[n] = MAX(D[n-i] + p[i]), 1<=i<=n 이다.

---

두번째 문제의 min 비교를 위한 배열초기값으로 문제조건을 활용한 1000*10000으로 초기화하는방법 -1로 초기화하는방법이있다. (d[i] = -1은 아직 정답을 구하지않았다는의미)