# 삽입 정렬

### ATM

#### Question - 11399

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2Fe6NkxEjAa1yZtGpZfcww%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-01%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.36.34.png?alt=media\&token=d3e708e4-7d68-4c12-a07f-968a72a41301)

#### Code

{% tabs %}
{% tab title="선택 정렬" %}
```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] S = new int[N];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        for (int i = 1; i < N; i++) {
            int insert_point = i;
            int insert_value = A[i];
            
            for (int j = i - 1; j >= 0; j--) {
                if(A[j] < A[i]) {
                    insert_point = j + 1;
                    break;
                }
                if(j == 0) {
                    insert_point = 0;
                }
            }
            
            for (int j = i; j > insert_point; j--) {
                A[j] = A[j-1];
            }
            A[insert_point] = insert_value;
        }
        
        S[0] = A[0]; // 합 배열 만들기
        for (int i = 1; i < N; i++) { 
            S[i] = S[i-1] + A[i];
        }
        
        int sum = 0; // 합 배열 총합 구하기
        for (int i = 0; i < N; i++) { 
            sum = sum + S[i];
        }
        
        System.out.println(sum);
    }
}
```


{% endtab %}

{% tab title="함수" %}
```java
import java.util.Arrays;
import java.util.Scanner;

public class N18_P11399_ATM {

    public static void main(String[] args) {
        // 전처리
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] A = new int[N];
        int[] S = new int[N]; // 합배열

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

        // 로직
        // A 배열을 작은 값 순서로 정렬해야 한다.
        // 삽입 정렬
        Arrays.sort(A);

        // 합배열
        // 누적 시간의 합이기 때문에 합배열을 사용해야 한다.
        S[0] = A[0];
        for (int i = 1; i < N; i++) {
            S[i] = S[i - 1] + A[i];
        }

        // 정답 도출
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += S[i];
        }

        // 출력
        System.out.println(sum);
    }
}

```
{% endtab %}
{% endtabs %}

#### Insight

#### Idea

* 그리디 알고리즘
* 정렬&#x20;
* 합배열&#x20;

#### reference
