[백준][java] 카드 구매하기11052

처음 시도한 방법

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],…)