삽입 정렬

ATM

Question - 11399

Code

선택 정렬

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);
    }
}

함수

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);
    }
}

Insight

Idea

• 그리디 알고리즘

• 정렬

• 합배열

reference