11399 ATM

그리디 알고리즘, 실버 4 문제이다.

그리디 알고리즘에 대해 복기하는 데 시간이 조금 걸렸을 뿐, 쉽게 풀 수 있는 문제였다.

 

그리디 알고리즘이란?

매 순간, 그 순간의 최적의 해를 선택하는 방식의 문제 해결 방식이다. 해당 순간에 "최적처럼 보이는" 해를 택하기 때문에 항상 최적의 해를 뱉는 것은 아닐 수 있다.

 

브루트포스, 그리디알고리즘, 다이나믹프로그래밍, 백트래킹에 대해 한 번 정리하는 글을 올릴 예정이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int n, sum = 0;
    private static int [] array;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;

        n = Integer.parseInt(br.readLine());

        array = new int[n];

        s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);

        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(array);

        for(int i = 0; i < n; i++){
            sum += (n - i) * array[i];
        }

        System.out.println(sum);
    }
}

입력받은 배열을 오름차순으로 정리하여, 가장 작은 인덱스(0)를 갖는 값을 n번 더해주고, 그 다음 인덱스(1)를 갖는 값을 n-1번 더해주고, ... , 가장 큰 인덱스를 갖는 값을 1번 더해주어 각 사람의 기다리는 시간의 합의 최솟값을 구했다.