백준 11052번 : 카드 구매하기

사고자하는 카드의 개수가 주어졌을 때, 가장 비싼 금액을 찾는 문제이다.

 

4장을 구매하려는데   1개에 5, 2개에 2, 3개에 8, 4개에 10 인 카드가 있다.

이 중 가장 4장을 가장 비싸게 구하는 방법은 1개에 5인 카드를 총 4개 구매하는 걸로, 20이 든다.

 

 

10

5 10 11 12 13 30 35 40 45 47

 

위의 예시에서

1개는 (1) 한 가지 방법뿐으로 5에 살 수 있다.

2개는 (1,1)을 구매하거나 (2)를 구매하는 방법이 있는데, 최댓값은 10으로 같다.

3개는 (1,1,1) , (1,2) , (3) 방법이,

4개는 (1,1,1,1) , (1,1,2) ,(1,3) , (2,2) (4)로 경우가 있으며

5개는 (1,1,1,1,1), (1,1,1,2), (1,1,3) , (2,3) , (2,2,1),  (1,4) , (5) 등의 방법이 있다.

이 경우에는 순서를 매길 필요가 없는 문제이다.

 

2개를 구매하고자 할 때에는 (1,1) 과 (2) 의 두 가지를 비교하면 된다.

이 둘 중 큰 값을 찾아 arr[2] 의 값을 경신시켜준다.

 

3개를 구매하고자 할 때에는 (1,1,1)과 (1,2)를 보아야 하는데,

위에서 (1,1)과 (2)의 값 중  큰 값을 arr [2]에 넣어놨기 때문에  (1,2)가 무조건 (1,1,1) 보다 큰 값이 된다.

결국, (1,2)과 (3)의 값을 비교해서 큰 값을 arr [3]에 넣어준다.

 

4개를 구매할 때에는 (1,1,1,1) , (1,1,2) , (1,3) , (2,2) , (4)를 봐야 한다.

하지만 이전에 작업한 결과를 보면

arr [2] 에는 2개를 구할 수 있는 최댓값이 들어있고,

arr [3] 에는 3개를 구할 수 있는 최댓값이 들어있다.

즉, (1,1,1,1) , (1,1,2) , (1,3)의 최대값은  (1,3) 의 값을 구하면 된다.

결국, (1,3), (2,2) , (4)  3가지의 경우를 보면 된다는 뜻이다.

 

 

식으로 정리해보면  n개를 구매할 때에는

n 값, (n-1) + (1) 값, (n-2) + (2)  값.......

이런 식으로 값을 비교해 나가며 최댓값을 갱신하는 것이 방법임을 알 수 있다.

 

import java.util.Scanner;

public class Main {
	private static Scanner sc;
	
	public static void main(String args[]) {
		sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[] = new int[n+1];
		
		for(int i=1;i<=n;i++) {
			arr[i]=sc.nextInt();
		}
		for(int i=2;i<=n;i++) {
			for(int j=i-1;j>=i/2;j--) {
				if(arr[i] < arr[j]+arr[i-j]) {
					arr[i]=arr[j]+arr[i-j];	
				}
			}
		}
		System.out.println(arr[n]);
	}	
}