[BJ11399] ATM

 백준 - ATM 

문제 링크

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

11399번: ATM

 

문제 입출력

5
3 1 4 3 2

32

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
	static int ans, N;
	static List<Node> list = new ArrayList<>();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 초기화
		N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int time = Integer.parseInt(st.nextToken());
			list.add(new Node(i, time));
		}

		// 시간 순으로 정렬
		Collections.sort(list, (e1, e2) -> e1.time - e2.time);

		// 풀이
		sol();

		// 출력
		System.out.println(ans);

	} // end main


	private static void sol() {

		for (int i = 0; i < N; i++) {
			ans += list.get(i).time; // 일단, 현재 시간 더하기

			// 이때까지 기다린 시간 더하기
			for (int j = 0; j < i; j++) ans += list.get(j).time;
		}

	} // end sol


	static class Node {
		int idx;
		int time;


		public Node(int idx, int time) {
			super();
			this.idx = idx;
			this.time = time;
		}


		@Override
		public String toString() {
			return "Node [idx=" + idx + ", time=" + time + "]";
		}

	} // end Node

}

그리디 알고리즘은 보통 정렬을 하면 풀리는 경우가 많다.

처음에는 문제를 보고 순열을 구해서 푸는 줄 알았는데, 그러면 시간 초과가 난다.

문제를 보니 기다리는 시간 배열을 작은 순서대로 정렬한 순서가 -> 최소합이 나오는 손님 번호의 순서가 된다.

따라서, sort() 메서드를 이용하여 정렬을 해준다.

그리고 나서 반복문을 2개 돌아 현재 기다린 시간과 + 이때까지 기다린 시간을 더해주면 최소값을 구할 수 있다.

 

 

 

 

 

 

 

 

 

#백준 ATM 자바 #백준 ATM java

---