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

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

 

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

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] p = new int[N + 1];
        int[] dp = new int[N + 1];
        StringTokenizer st =new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            p[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = p[1];

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

        System.out.println(dp[N]);
    }
}

 

풀이는 간단하다. 

 

N=2 라고 가정했을때 1개짜리 + 1개짜리, 0개짜리 + 2개짜리 이렇게 나눠진다. 그럼 이 들을 점화식으로 계산해보면 

dp[j] + p[i-j] 로나오게 된다.  이떄 dp[i] 랑 max 비교해서 최대값을 넣어주면서 계사하면 끝난다.