'greedy'에 해당되는 글 1건

임의의 사람 N 명과 각 사람들이 ATM에서 돈을 뽑는데 걸리는 시간 Pi가 각각 input으로 주어진다.

이때 각 사람들이 모두 돈을 뽑는데 걸리는 시간의 합의 최솟값을 구하라.

Pi가 작은 사람이 순서가 뒤로 갈수록 기다리는 시간이 증가하는것을 알 수 있다.

그 이유는 뒤에 위치한 사람은 앞에 위치한 사람이 ATM에서 소모하는 시간만큼을 추가로 기다리기 때문이다.

따라서 이 문제의 효율적인 해법은 오름차순으로 sort한 후에 기다린 시간을 return해주면 된다.

import java.util.Arrays;
import java.util.Scanner;

public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int arr[] = new int[N];
        int sum = 0;

        for(int i=0;i<N;i++) {
            arr[i] = scanner.nextInt();
        }
        scanner.close();    
        Arrays.sort(arr);

        for(int j=1;j<=N;j++) {
            for(int k=0;k<j;k++) {
                sum += arr[k];
            }
        }

        System.out.print(sum);
    }

}

위의 코드에서는 Input값을 전달받는데에 Scanner를 이용하였지만, BufferReader를 이용하면 3배 가까이 시간을 줄일 수도 있다.