[백준] 온라인 저지 12845번 : 모두의 마블(Java), 그리디

카드 합성을 레벨이 높은 순서대로 하면 유리하므로 그리디 알고리즘을 사용해 풀이한다.

 

배열을 내림차순으로 정렬한 후, 배열을 순회하며 각 레벨과 골드를 계산해준다.

배열 순회 시, 다음 차례의 레벨을 현재 레벨(더 높은 레벨)로 교체시켜주고, 두 레벨의 합산 값을 골드로 계산해주면 된다.

 

import java.util.*;

public class P12845_모두의마블 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Integer[] arr = new Integer[N];
        int answer = 0;

        for(int i =0; i<N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr, Collections.reverseOrder());

        for(int i=0; i<N-1; i++) {
            int level = arr[i];
            answer += arr[i] + arr[i+1];
            arr[i+1] = level;
        }
        System.out.println(answer);
    }
}