백준 11052 / 카드 구매하기

문제

풀이

설명

조건 : 카드 N개를 구매해야 한다.
카드팩은 총 N가지 종류가 존재하고 i번째 카드팩은 i개의 카드를 담고 있으며, 가격은 P[i]원 이다.
카드 N개를 구매하는 비용의 최대값을 구하는 문제
여기서 카드 N개를 구매하는 비용의 최대값을 D[N]이라고 하자.

카드팩 하나씩을 구매하면서 마지막 카드팩을 샀을 때 카드 N개를 딱 맞게 사야하는 조건을 충족해야 한다.
따라서 마지막 구매 카드팩에 든 카드가 i개라고 한다면,
마지막 이전까지 구매한 카드 개수는 N-i개 라고 할 수 있다.

그렇다면 카드 N-i개를 구매하는 비용의 최대값은 D[N-i]이며
마지막에 구매한 카드팩의 카드 갯수는 아직 알 수 없으므로 p[i]이다.

D[N] = max(D[N-i]+p[i])

코드

Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        int[] a = new int[n+1];
        
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        
        int[] d = new int[n+1];
        
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {
            	
                if (d[i] < d[i-j] + a[j]) {
                    d[i] = d[i-j] + a[j];
                }
            }
        }
        System.out.println(d[n]);

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/11052