문제 11399 ( Java ) - ATM 문제

ATM 문제

 

그리디 알고리즘으로 푸는 문제이다.

 

그리디 알고리즘을 정의를 다시 생각해보자. 현 상황에서 최적의 선택을 하는 과정을 정답이 나올때까지 반복하는알고

 

리즘이 그리디 알고리즘이다. 이 알고리즘을 문제에 적용해보자.

 

문제를 보면 N 명의 사람이 있고, 각 사람이 돈을 인출하는데 걸리는 시간이 Pi 라고 한다. 이 문제에 그리디 알고리즘을 

 

적용하면 현재 가장 돈을 인출하는데 걸리는 시간이 적은 사람을 선택하고, 선택한 사람을 제외한 사람들중에서 가장 돈

 

을 인출하는데 걸리는 시간이 적은 사람을 선택하는 과정을 N번 반복하면 된다.

 

 

이를 코드로 구현하기 위해서는 N개의 Pi를 배열에 저장하고, 배열을 오름차순으로 정렬시킨 다음 적은 숫자부터 선형으

 

로 골라주면 된다.

 

 

코드

 

import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
 
  public static void main(String []args) {
 
    Scanner sc = new Scanner(System.in);
 
    int N = sc.nextInt();
 
    int [] arr = new int[N];
 
    for ( int i = 0; i < N ; i++ ) {
      arr[i] = sc.nextInt();
    }
 
    Arrays.sort(arr);
    
    int sum = 0;
    int sum2 = 0;
    for ( int Pi : arr ) {
      sum += Pi;
      sum2 += sum;
    }
 
    System.out.print(sum2);
  }
} 
 

 

 

결과