[백준/자바] 11399 ATM 인출 시간 계산하기

[백준/자바] 11399 ATM 인출 시간 계산하기

 

📌 문제 

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [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분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi
가 주어진다. (1 ≤ Pi ≤ 1,000)

 

 

📣 출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

문제가 길지만 요구하는 것은 최소값을 구하라는 것이다.

 

문제에서 제시된 예시를 손 풀이로 나열해보면 다음과 같다. 

 

 

이로부터 확인할 수 있는 규칙은 

 

기다리는 시간이 가장 작은 순서로 나열하면 전체 시간 역시 최소값이 나온다는 것이다. 

 

인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 재배열 하는 방식을 그리디 방식이라 할 수 있다. 

 

삽입 정렬 알고리즘을 사용해서 풀수 있다.

 

이때 자바의 ArrayList의 기능으로 인덱스와 함께 특정 위치에 삽입이 가능하므로 이를 활용한다. 

 

1) 사람 수를 받는다

 

2) 사람별 시간을 받아 배열로 만든다.

 

3) 삽입정렬 알고리즘을 구현한다. 

 

로직은 다음과 같다. 

- 새로운 배열 (sorted)에 위에서 만든 사람별 시간을 넣되

- 0부터 시작하는 인덱스를 반복하고

- 만약 현재 들어가는 것이 x번째에 존재하는 값보다 크다면 그대로 들어가고 

- 작다면 해당 위치에 기존의 것을 밀어내면서 들어간다. 

 

4) 합배열로 만든다. 

 

5) 전체를 합한 결과를 리턴한다. 

 

 

 

 

 

 

 

💡 코드 구현하기

 

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 입력 후 배열로 보관하기
		Scanner sc = new Scanner(System.in);
		int peopleNum = sc.nextInt();
		List<Integer> waitingLine = new LinkedList<>();
		List<Integer> sortedLine = new LinkedList<>();
		for (int person =0; person < peopleNum; person++){
			waitingLine.add(person, sc.nextInt());
		}

		// 삽입정렬 알고리즘
		for (int cnt = 0; cnt < peopleNum; cnt++){
			insertSort(sortedLine, waitingLine.get(cnt));
		}

		// 합배열 알고리즘
		int[] sumArray = new int[peopleNum];
		sumArray[0] = sortedLine.get(0);
		for (int idx = 1; idx < peopleNum; idx ++){
			sumArray[idx] = sumArray[idx-1] + sortedLine.get(idx);
		}

		// 더하여 결과 출력
		int answer = 0;
		for (int idx = 0; idx < peopleNum; idx++){
			answer = answer + sumArray[idx];
		}
		System.out.println(answer);
	}

	/**
	 * 3) 삽입정렬 알고리즘을 구현한다.
	 * 로직은 다음과 같다.
	 * - 새로운 배열 (sorted)에 위에서 만든 사람별 시간을 넣되
	 * - 0부터 시작하는 인덱스를 반복하고
	 * - 만약 현재 들어가는 것이 x번째에 존재하는 값보다 크다면 그대로 들어가고
	 * - 작다면 해당 위치에 기존의 것을 밀어내면서 들어간다.
	 */
	public static void insertSort(List<Integer> sortedLine, int personTime){
		for (int idx = 0; idx < sortedLine.size(); idx++){
			if (sortedLine.get(idx) > personTime){
				sortedLine.add(idx, personTime);
				return;
			}
		}
		sortedLine.add(personTime);
	}
}

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편