백준 11399 그리디 알고리즘

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

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> WaitingLine(n);
	for (int i = 0; i < n; i++)
	{
		cin >> WaitingLine[i];
	}
	//for (auto a : WaitingLine) cout << a << " ";
	sort(WaitingLine.begin(), WaitingLine.end());
	//for (auto a : WaitingLine) cout << a << " ";
	int temp = 0;
	int MinSum=0;
	for (int i = 0; i < n; i++)//1 2 3 3 4
	{
		temp += WaitingLine[i];
		MinSum += temp;
	}
	//1
	//1+2 =4
	//1+2+3 =10
	//1+2+3+3 =19
	//1+2+3+3+4 =13
	cout << MinSum << endl;

	return 0;
}

❌ 순열로 풀면 비효율적! (Brute-force 접근 문제점)

순열(모든 경우의 줄 서는 순서)을 사용하여 해결하는 방법도 가능하지만, 너무 비효율적

순열을 이용한 풀이 방식

1. N명의 사람이 줄을 서는 모든 경우(순열)를 구한다. → O(N!)
2. 각 순열에 대해 대기 시간을 계산한다.
3. 최솟값을 찾는다.

💡 N이 1,000일 때, 순열의 경우의 수는 1000!(팩토리얼)이므로 현실적으로 계산 불가능! 😱
따라서, 그리디 알고리즘(Greedy Algorithm)을 사용하여 O(N log N) 시간복잡도로 해결하는 것이 최적

---

🚀 최적의 해결 방법: "그리디 알고리즘"

핵심 아이디어

1. "대기 시간이 짧은 사람이 먼저 처리되면 전체 합이 최소가 된다."
   • 즉, Pi를 오름차순으로 정렬하여 처리하면 최소값을 얻을 수 있음.
2. 정렬 후, 누적합을 계산
   • 정렬한 뒤 앞에서부터 누적합을 구하면 최솟값을 빠르게 구할 수 있음.

---

✅ 최적화된 풀이 (O(N log N))

📌 알고리즘 단계

1. Pi를 오름차순 정렬.
2. 누적합을 구하면서 전체 합을 계산.

---

 

입력

5
3 1 4 3 2

정렬 후

1 2 3 3 4

누적 대기 시간 계산

1  → 1
1+2 = 3  → 1+3
1+2+3 = 6  → 1+3+6
1+2+3+3 = 9  → 1+3+6+9
1+2+3+3+4 = 13  → 1+3+6+9+13

✔ 출력값: 32

---

📌 시간 복잡도 분석

• 정렬: O(N log N)
• 누적합 계산: O(N)
• 총 시간 복잡도: O(N log N) (💡 순열(O(N!))보다 훨씬 빠름!)

---

🔥 결론

✅ 순열(O(N!))을 사용하면 시간 초과 → 대신 O(N log N) 그리디 방식 사용!
✅ 작은 값부터 먼저 처리하면 전체 최소 대기 시간을 만들 수 있음!
✅ 정렬 + 누적합 활용하여 최적해를 빠르게 구할 수 있음! 🚀