🔍 Problem

11399 ATM

---

📃 Input&Output

---

📒 해결 과정

가. 오름차순 정렬하여 이전에 더해지는 값을 최소로 만든다.

나. 각각의 합을 전부 더한다.

예제에서는 다음과 같다.

---

💻 Code

import java.util.Arrays;
import java.util.Scanner;


public class P11399 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

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

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

        Arrays.sort(arr, (a, b) -> a - b);


        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                res += arr[j];

            }
        }

        System.out.println(res);
    }
}

---

🎸 기타

가. 그리디 알고리즘이란?

조건 1. 현재선택이 미래에 영향을 주지 않는다.
조건 2. 부분 최적해가 모이면 전체의 최적해가 된다.

현재 최적값을 구하고 다음 단계의 최적해를 각각 구하여 전체 최적해를 구하는 것이다. 현실적으로 현재 최적값이 전체적으로 봤을 때 항상 정답이라고 할 수 는 없지만, 정답과 유사한 값이 필요한 경우나 현재 최적값들의 합이 전체 최적해와 동일할 때 사용할 수 있다.

나. 자바 정렬

Integer[] arr = new Integer[N];


Arrays.sort(arr, (a,b) -> a-b) // 오름차순
Arrays.sort(arr, (a,b) -> a+b) // 내림차순

람다식을 사용하여 오름 차순 내림차순 정렬을 할 수 있다.

a+b : 오름차순
a-b : 내림차순

---

🤔 느낀점

그리디 알고리즘은 "최적해는 각 구간 최적값들의 합이다"라는 개념을 사용하여 DP나 완전 탐색의 모든 해를 구하는데 많은 시간이 든다는 단점을 극복한 알고리즘이다.