[C++] 백준 11399 ATM

 

www.acmicpc.net/problem/11399

11399번: ATM

 

1. 서론

이 문제는 그리디 알고리즘으로 풀 수 있다.

그리디 알고리즘이란 매 순간 최적의 방법을 선택하는 것이다.

결과적으로 최적의 방법은 아닐지 몰라도 고를 수 있는 선택지 중에서 가장 최적의 방법을 고르는 것이다.

 

2. 문제 풀이

사람들이 은행 ATM 기기 앞에 줄을 서있다. 사람들은 각각 돈을 인출하는 데 걸리는 시간이 다르다. 그러므로 어떤 사람이 어떤 순서로 돈을 인출하는지에 따라서 기다리는 시간의 합이 달라진다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는게 문제이다.

 

예제로 예를 들자면 각각 

 

3 1 4 3 2

 

시간이 걸리는 사람들이 있다. 그렇다면 최소 시간은 

 

1 2 3 3 4 -> 1 + 3 + 6 + 9 + 13 = 32

 

이런식으로 32분이 최소 시간이 된다. 

 

누적시간이 적게 걸리게 하기 위해서는 인출하는데 시간이 오래걸리지 않는 사람 순서대로 세워야 한다. 그래야 시간의 합이 최솟값이 될 수 있다. 따라서 배열을 입력받고 정렬을 한 뒤에 합을 구한다.

 

3. 코드 설명

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, i, a[1000], tmp = 0, sum = 0;

    cin >> n;

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
        
    sort(a, a + n);

    for (i = 0; i < n; i++)
    {
        tmp += a[i];
        sum += tmp;
    }
    
    cout << sum << endl;
}

 

사람의 수를 입력 받고, 각각 인출하는 시간을 입력 받는다. 정렬 후, 누적합을 구한다.