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

문제 출처 : https://www.acmicpc.net/problem/11052

이 문제는 다이나믹 프로그래밍으로 풀 수 있다.

문제가 장황하여 주의력이 산만해지지만 침착하게 읽어보자. 카드팩의 배열이 배열의 인덱스는 카드의 갯수이고 배열의 값은 카드의 금액이다. 이 두가지 정보가 한 배열에 들어 있기 때문에 조금 헷갈릴 수 있다. 

import java.util.*;
 
public class Q11052 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] card = new int[n+1];
        int[] d = new int[n+1];
 
        for (int i = 1; i <= n; i++) {
            card[i] = sc.nextInt();
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if(d[i] < card[j] + d[i-j]) {
                    d[i] = card[j] + d[i-j];
                }
            }
        }   
 
        System.out.println(d[n]);
    }
}

for 문 안의 배열은 인덱스가 중요하다. 마지막 구매하는 카드를 중점으로 생각해보면 card[j]를 구매했을 때 그 이전에 구매한 것은 d[i-j]이다. d[i-j]는 이미 구해진 것으로 가정한다. d 배열은 카드 n개를 구매하는 최대 비용이므로 d[i-j]는 j개의 카드 구해만 것을 제외한 최대 비용이다.