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

문제

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

풀이

 f(n)을 n개의 카드를 구매할 때의 최대 가격이라고 정의하자. 이 경우 f(n) = MAX( f(n-k) + prices[k] ) ( 1<= k <= n) 이다. 따라서 for문을 이용하여 memo[n]에 f(n)의 값을 기록하면 된다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] prices;
    public static int[] memo;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        prices = new int[N+1];
        memo = new int[N+1];

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

        /*
            f(n) : n개의 카드를 구매할 때의 최대 가격
            f(n) = Max(f(n-k)+prices[k]) (1<=k<=n)
         */
        calculateMaxPrice(N);
        int result = getMaxPrice(N);
        bw.write(String.valueOf(result));
        bw.flush();

    }
    public static void calculateMaxPrice(int n){
        for(int i = 1 ; i <=n; i++){
            memo[i] = prices[i];
            for(int j = 1; j< i ; j++){
                int tempPrice = memo[i-j] + prices[j];
                if(tempPrice> memo[i]) memo[i] = tempPrice;
            }
        }
    }
    public static int getMaxPrice(int n){
        return memo[n];
    }
}