[백준 17298] ATM (삽입정렬 사용)

🔗 문제

https://www.acmicpc.net/problem/11399

11399번: ATM

📝 풀이

1. 기준위치 값으로 삽입할 위치 찾기
2. 삽입할 위치 ~ 기준위치의 범위의 값들 오른쪽으로 한칸 씩 자리 이동
3. 삽입할 위치에 기준 값 넣기
4. 총 합 구하기

💻 코드

package org.kyhslam.bakjun.month_11;

import java.util.Scanner;

public class p11399 {

    public static void main(String[] args) {

        //5
        //3 1 4 3 2

        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 += S[i];
        }
        System.out.println(sum);
    }

}