백준 java) 11399번 문제 ATM

문제를 한번 같이 볼까요?

www.acmicpc.net/problem/11399

11399번: ATM

문제를 읽어보면

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분 만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

이런 식으로 구현해야 한다.

 

필자는 자바로 구현했습니다.

import java.util.*;

public class Main{
	 static int N;
	public static void main(String[] arg) {
		Scanner input = new Scanner(System.in);
		N = input.nextInt();
		int[] arr = new int[N];
		for(int i=0;i<N;i++) {
			arr[i] = input.nextInt();
		}
		ATM(arr);
	}
	
	private static void ATM(int[] array) {
		int[] arr = new int[N];
		Arrays.fill(arr, 0);
		int temp;
		int result=0;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++) {
				if(array[i]<array[j]) {
				temp = array[i];
				array[i] = array[j];
				array[j] = temp;
				}
			}
		}
		for(int i =N-1;i<N;i--) {
			 for(int j =0;j<i+1;j++) {
				arr[i] += array[j];
				 
			 }
		}
		for(int i=0;i<N;i++) {
			result += arr[i];
		}
		System.out.print(result);
	}
}

이러한 식으로 따로 함수를 제작하여 최적의 해를 구하기 위해 정렬 알고리즘을 사용했습니다. 시간 복잡도는 빅오 표기법으로 O(N^2)입니다. 모르는 부분이 있으면 댓글로 달아주세요~