처음 시도한 방법

public class 카드구매하기11052 {
	static int pay = 0;
	static int max = 0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n];
		for(int i = 0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		result(n, arr);
		System.out.println(max);
	}
	private static void result(int n, int[] arr) {
		if(n==0) {
			if(max<pay) {
				max=pay;
				pay = 0;
			}else {
				pay = 0;
			}
		}else {
			for(int i = 0 ;i<arr.length; i++) {
				if(n-(i+1)>=0) {
					n = n-(i+1);
					pay += arr[i];
					result(n, arr);
					
					n = n+(i+1);
				}else {
					break;
				}
				
			}
		}
		
	}

	
}

트리 구조로 구현하였으나 시간초과로 실패했다.

하지만 보다시피 이렇게 구현하면 1+2와 2+1이 중복되는 것을 알 수 있다.

구글링을 통해 다른 방법을 찾았다.

일반항 구하기

public class 카드구매하기11052_2 {

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

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

		System.out.println(d[n]);
	}

}

n이 3일 경우
- i 가 1일 경우
  - d[1] 은 d[1]과 d[0]+arr[1]중 큰 숫자가 된다.
  - d[1] = 0이고, d[0]+arr[1]은 0보다 크므로 후자가 된다.
- i가 2일 경우
  - d[2]와
    - d[1]+arr[1] → 카드를 1개 뽑을 경우 최대값과 카드가 1개 들어있는 팩 하나
    - d[0]+arr[2] → 카드가 2개 들어있는 팩 하나
    - 위의 두 가지 경우의 수를 비교하여 큰 값이 저장된다.
- i가 3일 경우
  - d[3]과
    - d[2]+arr[1] → 카드가 2개 뽑을 경우 최대값과 카드가 1개 들어있는 팩 하나
    - d[1]+arr[2] → 카드를 1개 뽑을 경우 최대값과 카드가 2개 들어있는 팩 하나
    - d[0]+arr[3] → 카드가 3개 들어있는 팩 하나
이 알고리즘이 내가 처음 시도한 알고리즘과 다른 것은
배열 d에 카드를 1개 부터 n개 뽑을 경우 최대로 지불할 값을 저장해 둔다는 것이다.
따라서 모든 경우의 수를 배열d에 미리 저장된 값으로 간편하게 비교할 수 있다.

n=1	d[1]
n=2	Math.max(d[2],…)
n=3	Math.max(d[3],…)