[Java] 백준 11052 카드 구매하기

11052 카드 구매하기 문제 링크

문제

#1

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

class Main {
    static int maxValue = 0;
    static int[] arr;

    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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        countMax(N, 0, 0);
        System.out.println(maxValue);
    }

    static void countMax(int N, int value, int card) {
        if(card==N) {
            maxValue = Math.max(maxValue, value);
            return;
        } else if(card>N) return;

        for(int i=0; i<N; i++) {
            countMax(N, value + arr[i], card + i + 1);
        }
    }
}

• 재귀로 풀음
• 모든 경우의 수를 다 계산해주는 방식
• 당연히 시간초과남

#2

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

class Main {
    static boolean[] value;
    static int maxValue = 0;
    static int[] arr;

    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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        countMax(N, 0, N);
        System.out.println(maxValue);
    }

    static void countMax(int N, int value, int card) {
        if(card==0) {
            maxValue = Math.max(maxValue, value);
            return;
        } else if(card<0) return;

        for(int i=card; i>0; i--) {
            countMax(N, value + arr[i-1], card - i);
        }
    }
}

• 계산하는 경우의 수를 줄임
• 처음에 가장 큰 수를 선택하여 그 수보다 작은 수만 고려
• 근데 그래도 시간초과남

#3

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

class Main {
    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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N+1];
        dp[1] = arr[1]; // 초기값 설정 : 1단계

        for(int i=2; i<=N; i++) {
            for(int j=i-1; j>=0; j--) {
                dp[i] = Math.max(dp[i], arr[i-j]+dp[j]);
            }
        }
        System.out.println(dp[N]);
    }
}

• 도움을 받음,,,
• 이전의 최대값을 dp로 저장함,,
• 코드가 간단해져서 열받음
  
• 일단은 성공..