백준 11052번: 카드 구매하기 [DP][다이나믹 프로그래밍] -Java

 

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

11052번: 카드 구매하기

 

카드팩 1개만 있을때 최대값

카드팩 2개가 있을때 최대값

카드팩 3개가 있을때 최대값을 구한다. 이전과 비교하며 Max를 취함.

 

<백준 11052번 Java코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		
		int card[] = new int[N+1];
		int dp[] = new int[N+1];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = i; j <= N; j++) {
				dp[j] = Math.max(dp[j], dp[j-i]+card[i]);
			}
		}
		
		System.out.println(dp[N]);
	}

}