[BOJ] 11399 ATM

문제

www.acmicpc.net/problem/11399

11399번: ATM

 

풀이

1) 시간 초과 코드

처음에 브루트 포스 방식으로 시간(ATM 걸리는 시간) 배열의 모든 경우의 수를 이용해 해봤던 코드이지만, 여지없이 시간초과가 떴던 방식이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//11399 ATM 문제
public class Main {
	static boolean[] visited;
	static int[] tmp;
	static int min = Integer.MAX_VALUE;
	
	public static int get_time(int[] time, int N) {
		int sum=0;
		int pre_sum=0;
		for(int i=0;i<N;i++) {
			pre_sum+=time[i];
			sum+=pre_sum;
		}
		return sum;
	}
	public static void permutation(int[] std, int depth, int N) {
		if(depth == N) {
			int time = get_time(tmp,N);
			min = min > time ? time : min;
			return;
		}
		for(int i=0;i<N;i++) {
			if(!visited[i]) {
				visited[i] = true;
				tmp[depth] = std[i];
				permutation(std,depth+1,N);
				visited[i] = false;
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		//시간 초과 코드
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] P = new int[N];
		String ps = br.readLine();
		StringTokenizer st = new StringTokenizer(ps," ");
		tmp = new int[N];
		visited = new boolean[N];
		
		for(int i=0;i<N;i++)
			P[i] = Integer.parseInt(st.nextToken());
		
		permutation(P,0,N);
		
		System.out.println(min);
	}

}

2) 개선 코드

시간 초과 시행착오 후 그리디 방식을 떠올렸다. 시간 배열을 오름차순으로 정렬하여 시간과 시간간의 차이를 최소로 하는 방식을 택해서 코드를 작성해봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//11399 ATM 문제
public class Main {	
	public static int get_time(int[] time, int N) {
		int sum=0;
		int pre_sum=0;
		for(int i=0;i<N;i++) {
			pre_sum+=time[i];
			sum+=pre_sum;
		}
		return sum;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] P = new int[N];
		String ps = br.readLine();
		StringTokenizer st = new StringTokenizer(ps," ");
		
		for(int i=0;i<N;i++)
			P[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(P);//오름차순
		System.out.println(get_time(P,N));
	}

}