[백준] 카드 구매하기 11052 - JAVA

문제

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

11052번: 카드 구매하기

풀이

DP 문제다. 카드 N개를 구매하는데 드는 비용의 최대를 구하는 문제이다.

 

카드 i개를 구매하는 방법은 어떻게 될까

• 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다.
• 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다.
• 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다.

...

일반화 시키면 D[i] = P[n] + D[i-n] 이다. 

코드

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		int arr [] = new int [n+1];
		int dp [] = new int [n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = arr[i];
		}
		
		for(int i=2;i<=n;i++) {
			for(int j=1;j<=i;j++) {
				dp[i] = Math.max(dp[i], dp[i-j]+arr[j]);
			}
		}
		
		System.out.print(dp[n]);
		
	}
	
    
   
}