[백준 11399] ATM (JAVA)

백준 11399번 문제  - ATM

11399번: ATM

---

문제 분석

 

 

 

ATM 기기는 하나뿐이다. 이를 사용하기 위해 사용자들은 기다린다. 사람들 모두가 사용을 끝내는 최소 시간을 구하고자 한다.

 

---

해결 키 포인트

 

최소 시간을 구하기 위해서는 사용자들의 ATM기 사용하는 순서가 적게 걸리는 사람이 먼저, 오래 걸리는 사람이 나중에 사용하도록 정렬해야한다.

 

• 사용시간에 따라 사용자 정렬 (사용시간 오름차순으로 정렬)
  • Arrays.sort()
  • 삽입 정렬 등
• 0부터 i번째까지 사용시간을 더한 합 배열 구하기
• 합 배열을 다 더해서 최종 모두가 사용을 끝내는 최소 시간을 구하기

 

---

Arrays.sort로 쉽게 정렬 가능하나 삽입 정렬 연습을 위해 사용

 

삽입 정렬 설명

 

선택 데이터를 현재 정렬도니 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심

 

Do it! 알고리즘 코딩 테스트 기본

 

---

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 사람별 P 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        int [] P = new int [N];
        for(int i=0;i<N;i++) {
            P[i] = Integer.parseInt(st.nextToken());
        }

        // P를 오름차순으로 정렬
        for(int i=1;i<N;i++) {
            // 현재 수 기억
            int currentP = P[i];

            // 해당 index 아래 수들만 확인
            for(int j=i-1;j>=0;j--) {
                // 큰 값은 값 변경
                if(P[j] > currentP) {
                    P[j+1] = P[j];
                    P[j] = currentP;
                }
                // 작은 값일 경우 이 이후 값 변경 후 break
                else {
                    P[j+1] = currentP;
                    break;
                }
            }
        }
//        Arrays.sort(P);

        int result = 0;
        int [] sums = new int [N];

        for(int i=0;i<N;i++) {
            if(i == 0)
                sums[i] = P[i];
            else
                sums[i] = sums[i-1] + P[i];

            result += sums[i];
        }

        System.out.println(result);
    }
}