11052

카드 구매하기

 

점화식

dp[i] = Math.max(dp[i], dp[i - j] + arr[j]);

 

의미, 돌다리 건너는 것과 동일하다, 대신 돌다리를 한번에 넘을 수 있는 경우에 제한이 없는것.

arr[] = 1, 5 ,6 7의 경우.

dp[1] = 1

dp[2] : max(dp[1] + arr[1] , dp[0] + arr[2])

dp[3] : max(dp[2] + arr[1] , dp[1] + arr[2], dp[0] + arr[3])

dp[4] : max(dp[3] + arr[1] , dp[2] + arr[2], dp[1] + arr[3] , dp[0] + arr[4])

dp[5] : max(dp[4] + arr[1],  dp[3] + arr[2], dp[2] + arr[3], dp[1] + arr[4], dp[0] + arr[5])

 

위의 점화식을 통해 모든 카드를 조합하여 구매하는 수( 돌다리를 건너는 경우의 수)를 구할 수 있다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static long[] dp;
	static int[] arr;

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

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

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

	}

}

ex)
10
1 1 2 3 5 8 13 21 34 55
55