백준 11399번 [ATM](C++) -yes6686- 티스토리

백준 문제 풀이: 11399 [ATM]

---

문제 링크: https://www.acmicpc.net/problem/11399

문제 설명:

이 문제는 ATM 앞에서 사람들이 돈을 인출하는 데 걸리는 시간의 합을 최소화하는 문제입니다. 각 사람이 돈을 인출하는 데 걸리는 시간이 주어질 때, 적절히 줄을 세워 기다리는 시간의 총합을 최소화해야 합니다.

입력:

• 첫 줄에 사람의 수 n이 주어집니다 (1 ≤ n ≤ 1000).
• 둘째 줄에는 n개의 정수로 각 사람이 돈을 인출하는 데 걸리는 시간이 주어집니다.

출력:

• 각 사람이 기다린 시간의 총합의 최소값을 출력합니다.

예시:

입력:
5
3 1 4 3 2

출력:
32

---

문제 해결 코드

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

int main() {
    int n;
    cin >> n;

    int arr[1001]; // 각 사람의 인출 시간
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 인출 시간을 오름차순으로 정렬
    sort(arr, arr + n);

    int totalTime = 0; // 기다린 시간의 총합
    int currentSum = 0; // 현재까지의 대기 시간

    for (int i = 0; i < n; i++) {
        currentSum += arr[i]; // 각 사람의 대기 시간 계산
        totalTime += currentSum; // 총 대기 시간에 추가
    }

    cout << totalTime; // 결과 출력
    return 0;
}

---

코드 설명

이 코드는 그리디 알고리즘을 사용하여 대기 시간의 합을 최소화합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: 대기 시간이 짧은 사람부터 먼저 인출하도록 정렬하면 총 대기 시간의 합이 최소화됩니다.
• 구현 세부사항:
  • sort(arr, arr + n): 인출 시간을 오름차순으로 정렬합니다.
  • currentSum: 현재까지의 대기 시간을 누적합니다.
  • totalTime: 각 사람의 대기 시간을 모두 합한 값입니다.
• 시간 복잡도 분석:
  • 정렬: O(n log n)
  • 대기 시간 계산: O(n)
  • 전체 시간 복잡도: O(n log n)

---

결과

코드는 주어진 입력에 따라 총 대기 시간의 합을 계산하여 출력합니다. 정렬을 통해 대기 시간의 합을 최소화하며, 효율적으로 문제를 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!