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

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

11052번: 카드 구매하기

 

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

카드팩을 N개의 가격이 주어지고, N번째 카드팩에는 N개의 카드가 들어있을 때 카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 문제

카드팩의 갯수 N : 1<=N<=1,000

각 카드팩의 가격 N : 1<=N<=10,000

 

2. 나의 방식대로 문제를 재정의 하자.

카드팩의 값을 조합해서 최대값을 구한다.

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

dp를 사용해서 문제를 해결한다.

dp[i]는 카드를 i개 살때의 최댓값을 저장한다.

모든 경우의 수를 비교해서 최대값을 저장한다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader이용

 

 

5. 주의할 점은 무엇인가?

 

 

6. 풀이 과정

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

public 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));
        
        Integer N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Integer[] packP = new Integer[N+1];
        int[] dp = new int[N+1];
        for (int i = 1; i <= N; i++) {
            packP[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 0;
        for (int i = 1; i <= N; i++) {//카드 i개 구매
            for (int j = 1; j <= i; j++) {
                dp[i] =Math.max(dp[i], dp[i - j]+packP[j]);
            }
        }
        

        bw.write(dp[N] + "\n");        
    

        bw.flush();
        br.close();
        bw.close();
    }

}

 

7. 개선점