[백준 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)

출력

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

 

예제 입력 1 복사

5
3 1 4 3 2

예제 출력 1 복사

32

 

문제 접근

문제 자체는 길지만 천천히 읽어보면 쉬운 문제인 것을 알 수 있을 것입니다.

입력된 '인출하는데 필요한 시간'을 보면 앞 사람이 빨리 끝나야 대기 시간이 줄어들 수 있으므로

오름 차순으로 정렬 후 대기시간을 누적으로 합하면 끝나는 문제입니다.

 

1. 각각의 사람들이 돈을 인출할 때 다른 사람의 개입이 없다는 점(독립성)

2. 앞 대기시간이 짧은 것이 전체적인 대기시간 또한 줄어들게 한다는 것 (전체 최적해가 부분 최적해를 만족)

을 통해 그리디 알고리즘의 특성을 만족한다고도 할 수 있습니다.

 

 

이 문제는 전형적인 활동 선택 문제이기도 합니다.

👌 활동 선택 문제란?

    한 사람이 하나의 활동을 할 때 + 최대한 많은 활동을 할 수 있는 수를 도출해내는 문제

 

실패 코드

import java.util.*;

class Time implements Comparable<Time> {
	public int time;
	
	// 매개변수 있는 생성자
	Time(int time) {
		this.time = time;
	}
	
	// 오름차순 정렬
	@Override
	public int compareTo(Time t) {
		return this.time - t.time;
	}
}

public class Atm {

	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		// 인출하는데 걸리는 시간을 담을 배열 선언
		int[] time = new int[n];
		// for문을 돌면서 인출시간 입력
		for(int i=0; i<n; i++) {
			time[i] = kb.nextInt();
		}
		//
		// Time<time> t = new Time<>();.....
		// 오름차순 정렬
		// Collections.sort(t);......

	}

}

굳이,, 좌표 정렬을 왜 사용했을까요?

어! 오름차순 정렬이네! 그럼 좌표 정렬이지~~~ 룰루 이런 의식의 흐름으로 적었던 것 같습니다.

 

그냥 Arrays.sort();  쓰면 되는데 하하 반영해서 다시 작성해보겠습니다.

 

성공 코드

import java.util.*;

public class Atm {
	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		// 인출하는데 걸리는 시간을 담을 배열 선언
		int[] time = new int[n];
		// for문을 돌면서 인출시간 입력
		for(int i=0; i<n; i++) {
			time[i] = kb.nextInt();
		}
		// 정렬
		Arrays.sort(time);
		
		// 누적합을 두개로 나눠서 선언(이전, 총)
		int beforeSum = 0;
		int totalSum = 0;
		
		for(int i=0; i<n; i++) {
			totalSum += time[i] + beforeSum;
			beforeSum += time[i];
		}
		System.out.println(totalSum);
	}

}

point 1.

중간에 이중 for문을 써서 누적을 해야하나 생각을 했었습니다. 하지만 알고리즘 문제를 풀때 이중for문은 최후의 보루로 되도록이면 쓰지 않는 것이 맞다고 배웠기에 한 번 더 고민을 해봤습니다.

 

sum을 하나로 가져가지 않고 이전의 누적합인 beforeSum과 최종 누적의 합인 totalSum으로 나누면 이중for문을 사용하지 않고도 가능할 것 같았습니다.

 

point 2.

여기서 주의할 점은 totalSum과 beforeSum의 위치가 바뀌면 안 된다는 것입니다.

total을 먼저 하고 before를 후에 위치시켜야 중복을 피할 수 있습니다.

for(int i=0; i<n; i++) {
			totalSum += time[i] + beforeSum;
			beforeSum += time[i];
		}

 

 

📢 정렬
하나의 요소 정렬 : Arrays.sort(arr)
둘 요소 정렬 : 좌표 정렬

 

 

 

알고리즘 문제 풀이도 결국에는 사람의 논리를 코드로 적은 것뿐입니다. 

생각을 논리적 효율적으로 한 후 코드로 한 줄 한 줄 표현해내는 원리를 문제를 하나씩 풀면서 익혀가려 합니다.