[백준] 11399번: ATM 풀이 및 해설(C++)

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

11399번: ATM

 

 

C++로 작성한 백준 문제 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)

출력

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

 

---

풀이

 

 

모든 사람이 돈을 인출하는데 걸리는 시간이 최소가 되려면, 빨리 인출할 수 있는 사람부터 인출하면 된다. 

돈을 인출하는 시간 기준으로 오름차순 순으로 대기시키면 필요한 시간의 합이 최소가 될 수 있다.

---

 

해답 코드 및 설명

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main()
{
    fastio;
    int n,ans=0;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    for(int i=0; i<n; i++){
        ans+=arr[i]*(n-i);
    }
    cout<<ans;

    return 0;
}

 

n에 사람 수를, 그리고 arr 벡터에 인출하는데 걸리는 시간을 넣는다.

그리고 sort를 통해 이를 오름차순으로 배열한다.

모든 사람이 뽑는데 걸리는 시간은 나보다 앞에선 사람들이 걸리는 시간의 합의 합이다.

즉 5명이 서 있을 때 맨 앞사람이 걸리는 시간은 총 5번 더해지고, 2번째 사람은 4번... 마지막 사람은 1번 이런 식이다.

그래서 for문을 통해 결과값 ans에 arr [i]*(n-i)를 더해준다.

 

 

---

 

헤매었던 부분 

딱히 없다.

 

 

 

 

---

 

마무리

걸리는 시간에 따라 오름차순으로 정렬해야 한다는 것이 중요하다.

정렬 후 이를 계산할 때 계속 나보다 앞사람의 값을 더해주는 이중 for문을 사용할 수도 있지만, 위의 코드처럼 for문 1개만으로 계산해 준다면 O(n^2)에서 O(n)으로 시간 복잡도를 줄일 수 있다.