[S4] 11399 : Java - ATM : 삽입 정렬

문제

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

11399번: ATM

 

접근방법

어떻게 하면 최솟값을 구할 수 있을까 생각을 했을 때, 누적시켜 더하는 특징에서 앞에 나오는 값들이 작을 때 최소가 될 것이다 생각을 했다. 그래서 오름차순 정렬을 이용하기로 하였다. 

 

풀이

입력

입력의 수가 최대 1001개 이므로 비교적 구현이 쉬운 스캐너로 구현하였다.

 	// 입력 받기
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int [] num = new int[N];
        for(int i=0; i<N; i++){
            num[i] = sc.nextInt();
       }

 

오름차순 정렬 - 삽입 정렬

정렬을 아무 정렬 방법이든 사용 가능하지만 책의 내용에 맞춰 삽입 정렬을 이용하였다. 삽입 정렬은 평균 O(n^2)의 시간 복잡도를 가지고 최선의 레코드일 때 O(n)의 시간 복잡도로 정렬이 어느 정도 완료된 상태에서 쓰면 유용한 정렬 기법이다.

	// 정렬 - 삽입 정렬
        int i,j;
        for(i= 1; i< N; i++){
            int key = num[i];
            for(j = i-1; j>=0&&num[j]>key; j--){
                num[j+1] = num[j];
            }
            num[j+1] = key;
        }

 

최솟값 구하기

값을 누적시키기 위해 sum 변수를 이용하여 i번 째 사람이 돈을 뽑는데 걸리는 시간을 구해주고, 모든사람의 시간을 누적 시켜 더하도록 minSum에 sum을 누적시켜 더하였다.

	// 최솟값 구하기
        int minSum = 0;
        int sum = 0;
        for(i=0; i<N; i++){
            sum += num[i];
            minSum += sum;
        }

 

출력

	// 결과 출력
        System.out.println(minSum);

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        // 입력 받기
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int [] num = new int[N];
        for(int i=0; i<N; i++){
            num[i] = sc.nextInt();
        }

        // 정렬 - 삽입 정렬
        int i,j;
        for(i= 1; i< N; i++){
            int key = num[i];
            for(j = i-1; j>=0&&num[j]>key; j--){
                num[j+1] = num[j];
            }
            num[j+1] = key;
        }

        // 최솟값 구하기
        int minSum = 0;
        int sum = 0;
        for(i=0; i<N; i++){
            sum += num[i];
            minSum += sum;
        }

        // 결과 출력
        System.out.println(minSum);

    }

}