[백준 #11399] ATM

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

 

문제

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

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P_1 = 3, P_2 = 1, P_3 = 4, P_4 = 3, P_5 = 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)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 P_i
가 주어진다. (1 ≤ P_i ≤ 1,000)

 

출력

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

 

예제 입력

5
3 1 4 3 2

 

예제 출력

32

 

해결 코드

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	//N명 사람들이 줄을 설 거임
	//각각 필요한 시간이 존재
	//기다리는데 필요한 시간이 최소가 되게 하여 그 합을 출력. --> greedy 문제
	//걸리는 시간이 짧은 사람부터 처리하는 것이 greedy 기준
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		
		int times[] = new int[n];
		for(int i=0; i<n; i++) {
			times[i] = scanner.nextInt();
		}
		
		Arrays.sort(times);
		
		int spentTimes[] = new int[n];
		
		spentTimes[0] = times[0];
		int sum = spentTimes[0];
		for(int i=1; i<n; i++) {
			spentTimes[i] = spentTimes[i-1] + times[i];
			sum += spentTimes[i];
		}
		
		System.out.println(sum);
		
	}

}

 

 

 

---

해당 문제를 해결하기 위해서는 Greedy 알고리즘을 사용하여 사람들이 줄을 설 때 기다리는 시간의 총합을 최소화하는 문제를 해결하는 것이 중요하다.

 

1. 로직 설명

1) 입력 단계:

• n을 입력받아 사람 수를 저장합니다.

• times[] 배열에 각 사람이 기다려야 할 시간을 입력받습니다.

2) 정렬 단계:

• Arrays.sort(times)를 사용해 기다리는 시간이 짧은 순서대로 정렬합니다.

• 예: 입력이 [3, 1, 4, 3, 2]인 경우, 정렬 후 [1, 2, 3, 3, 4]

3) 누적 합 계산 단계:

• Greedy 전략에 따라 대기 시간이 짧은 사람부터 줄을 서도록 합니다.

• spentTimes[] 배열에 누적 대기 시간을 저장합니다. 아래와 같이 DP 로직을 사용했습니다.

• spentTimes[0] = times[0]

• spentTimes[i] = spentTimes[i-1] + times[i] 

 

 

 

---

2. 자료구조 분석

 

1) 배열 (Array)

사용된 배열:

• int times[]: 각 사람이 기다려야 할 시간을 저장.

• int spentTimes[]: 각 사람이 대기하면서 실제로 소요된 시간을 저장.

특징 및 역할:

• 고정된 크기로 메모리에 연속적으로 할당되므로 **인덱스 접근이 O(1)**로 매우 빠르다.

• 여기서 times[] 배열은 사용자 입력을 받아 각 사람이 걸리는 시간을 저장한다.

• spentTimes[] 배열은 누적 대기 시간을 계산하는 데 사용된다.

공간 복잡도: O(n)

배열 2개(times[], spentTimes[])가 n개의 요소를 저장하므로 총 O(2n)이지만 상수는 무시하여 O(n)으로 본다.

 

 

 

---

3. 알고리즘 분석

 

1) 정렬 (Sorting)

사용된 메서드:

Arrays.sort(times);

 

동작 원리:

• Arrays.sort()는 Dual-Pivot QuickSort 알고리즘을 사용하며, 시간 복잡도는 O(n log n)이다.

• 이 문제에서 정렬의 목적은 기다리는 시간이 짧은 사람부터 줄을 세우는 것으로, 대기 시간을 최소화하기 위한 Greedy 전략을 구현한 것이다.

이유:

• 기다리는 시간이 짧은 사람부터 처리해야 나중에 오는 사람이 기다리는 시간이 최소화된다.

예를 들어 [1, 2, 3] 순서로 처리하면 총 대기 시간이 [1, 3, 6]으로 최소가 된다.

 

---

 

2) 누적 합 계산 (DP, Prefix Sum)

• 사용된 부분:

spentTimes[0] = times[0];
int sum = spentTimes[0];
for(int i=1; i<n; i++) {
    spentTimes[i] = spentTimes[i-1] + times[i];
    sum += spentTimes[i];
}

 

동작 원리:

• 각 사람이 기다린 시간은 이전 사람들의 대기 시간의 누적합이다.

• 예를 들어 정렬된 배열 [1, 2, 3]이라면, 각 사람의 대기 시간은 [1, 1+2, 1+2+3]이 된다.

시간 복잡도: O(n)

for문을 한 번 순회하면서 누적합을 계산한다.

공간 복잡도: O(n)

결과를 저장하기 위해 spentTimes[] 배열이 추가로 필요하다.

 

 

 

---

4. 전체 시간 복잡도

• 정렬: O(n log n)

• 누적 합 계산: O(n)

• 따라서 전체 시간 복잡도는 O(n log n)이다. (O(n log n) + O(n) = O(n log n))

 

 

 

---

5. 전체 공간 복잡도

• times[]와 spentTimes[] 배열 2개 사용 → O(n)

• 입력 크기에 비례하는 공간만 사용하므로 공간 복잡도는 O(n)이다.

 

 

 

---

6. Greedy 전략 분석

이 문제는 Greedy 알고리즘으로 해결한 대표적인 예다.

 

Greedy 선택 기준:

기다리는 시간이 짧은 사람부터 줄을 세운다. 이렇게 해야 이후에 오는 사람들이 대기하는 시간을 최소화할 수 있다.

 

정당성:

이 선택 기준은 부분 문제들이 최적화되면 전체 문제도 최적화된다는 Greedy Choice Property를 만족한다. 또한, 앞부분의 선택이 뒷부분에 영향을 주지 않는 Optimal Substructure 성질도 만족한다. Greedy 알고리즘이 항상 최적의 해를 구하는 것은 아니지만, 이 문제에서는 올바르게 동작한다. 그 이유는 기다리는 시간이 짧은 사람부터 처리하면 다음 사람에게 영향을 최소화할 수 있기 때문이다.