[Java] 11052 카드 구매하기

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

N개의 카드팩을 구하기 위한 최대 가격이므로 동적 프로그래밍, dp를 사용한다..
dp[i] = i개의 카드팩을 구하기 위한 최대 가격 으로 출력해야겠지?
따라서 dp[i] = max(dp[i], i장일때 다른 값)

그럼 이제 i장일 때 다른값일 경우를 생각해보자.

예를 들어 arr = [5,1,3] , 1장일 때 가격 5원 , 2장일 때 가격 1원, 3장일 때 가격 3원 상황을 가정하고,
3장을 사야한다고 할 때 최댓값은 5원짜리 1장을 3번 구입하여 15원이 된다.
계산을 해보자.

카드가 1장일 때는 당연히 arr[1] 의 값이므로, dp[1] = 5 가 된다.

카드가 2장일 때 , 즉 dp[2] 카드를 2장 살 수 있는 경우의 수는
1. 2장 arr[2] = 1
2. 1장을 2번 arr[1]*2 = 10
이므로, 우리는 1장을 2번 사야한다.

이 값은 dp[1] + arr[1] 로 이루어질 수 있다.
즉, dp[1] = 카드가 1장일 때 최댓값이며 arr[1] = 1장을 더 살 수 있으므로 더해준다.

이어서 카드가 3장일 때는 더 이해하기 쉬울것이다
dp[3] , 카드를 3장 구할 수 있는 경우의 수는
1. dp[2] + arr[1] 카드 2장의 최댓값과 카드1장의 가격 = 15
2. dp[1] + arr[2] 카드 1장의 최댓값과 카드2장의 가격 = 6
3. dp[0] + arr[3] 카드 0장의 최댓값과 카드3장의 가격 = arr[3] = 3 이므로 = 3
가 된다.

이걸 식으로 표현하면 (여기서 j는, 1부터 i까지 반복문을 도는 변수 )
dp[3] 이므로 i=3, j=1,2,3
위와 비교해서 1번을 보면 i=3 이고 j=1일 때,
dp[2] + arr[1] 는 dp[3-1] + arr[1] == dp[i-j]+arr[j] 임을 알 수 있다.
현재 카드수에서 j를 빼고, j에 해당하는 기존 카드값을 가져와 더해주는 단순한 원리이다!

따라서 dp[i-j] + arr[j] 이러한 식이 나오고,
점화식은 max(dp[i] , dp[i-j] + arr[j])

3. 코드

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

public class Main {

	static int N ;
	static int[] arr ;
	static int[] dp;
	static int total;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		dp = new int[N+1];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<N+1;i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

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