[BOJ] 11052. 카드 구매하기

DP를 사용하는 문제이다.

이 문제는 DP를 사용하는 문제인데 다음과 같은 점화식을 가진다.

dp[n]= max(dp[i] + cost[n-i], cost[n]) (1 <= i < n)

i가 1부터 n-1까지 변하기에 이 부분을 for 문으로 해결해 주었다. 위와 같은 점화식을 이용하면 n번째에서의 최대값을 구할 수 있다.

package boj.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_11052_카드구매하기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int N=Integer.parseInt(br.readLine());
        int[] dp=new int[N+1];
        int[] cost=new int[N+1];
        
        
        st=new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++)
            cost[i]=Integer.parseInt(st.nextToken());
        
        dp[1]=cost[1];
        
        for(int i=2;i<=N;i++) {
            dp[i]=cost[i];
            for(int j=1;j<=i-1;j++) {
                dp[i]=Math.max(dp[i], dp[j]+cost[i-j]);
            }
        }
        
        System.out.println(dp[N]);
        
    }
}