[백준] 11399번 ATM 자바

문제 (실버3)

 

11399번: ATM

 

 

 

문제 풀이

 

처음에 순열 함수를 따로 만들어서 모든 순열 경우의 수를 구해서 그 합을 구해 작은 값을 찾아가는 식으로 풀었다.

 

	public static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
		if(depth == r) {
			int sum = 0;
			for(int i = 0; i < r; i++)
				for(int j = 0; j <= i; j++)
					sum += time[output[j]];
			
			if(sum < result)
				result = sum;
			//System.out.println(sum);
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(visited[i] != true) {
				visited[i] = true;
				output[depth] = arr[i];
				permutation(arr, output, visited, depth+1, n, r);
				output[depth] = 0;
				visited[i] = false;
			}
		}
	}

 

 

당연히 시간초과가 떴다...^^

최소 합을 구하기 위해 그냥 시간이 적은 사람부터 누적해 나가면 되는 것을 왜 이렇게 풀었는지 모르겠다ㅠ

Arrays.sort()함수를 이용하여 오름차순 정렬하여 누적합을 구해 출력했다.

 

 

 

 

소스 코드

 

public class b_11399 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] time = new int[n];
		int sum = 0;
		
		for(int i = 0; i < n; i++) 
			time[i] = sc.nextInt();
		
		Arrays.sort(time);
		
		for(int i = 0; i < n; i++)
			for(int j = 0; j <= i; j++)
				sum += time[j];
		
		System.out.println(sum);
		sc.close();
	}
}