[BOJ] 11399 ATM - JAVA

1. 문제

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

11399번: ATM

인하 은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다. 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

---

2. 풀이

두가지 방법으로 풀이했다.

첫 번째는 <직전에 얼마나 기다렸는지+직전 사람이 돈 인출하는 데 걸린 시간 = 현재 사람이 기다리는 시간> 식을 이용해서 풀었다.

두 번째는, 총합계에서 1번 사람이 돈을 인출하는 시간은 N번, 2번 사람은 N-1번, N번 사람은 N-N(=0)번 더한 결과라는 것을 이용해서 구했다.

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

public class BOJ_11399_ATM {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] time = new int[N];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for (int i = 0; i < N; i++) time[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(time);

      int sum = 0;
      //첫번째방법
      int[] wait = new int[N+1];
      for (int i = 1; i <= N; i++) {
         wait[i] = wait[i-1]+time[i-1];
         sum += wait[i];
      }

      //두번째방법
      sum = 0;
      for(int i=0;i<N;i++){
         sum += time[i]*(N-i);
      }

      System.out.println(sum);
   }
}

---

3. 결과

윗줄이 첫번째 방법, 아랫줄이 두번째 방법이다.