[백준] 11399번 : ATM [C/C++]

#문제

11399번: ATM

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

11399번: ATM

 

---

#접근방법

정렬을 하고 반복문을 돌면서 시간의 합을 구하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[1005];

int main(){
    int n;
    int ans = 0;

    scanf("%d",&n);

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

    sort(arr,arr+n);

    for(int i=0;i<n;i++)
        ans += arr[i]*(n-i);

    printf("%d",ans);

    return 0;
}

 

ATM에서 각 사람이 돈을 인출하는데 걸리는 시간의 최솟값을 구하려면 인출하는데 시간이 적은순으로 뽑으면 된다.

 

따라서 arr배열에 각 사람이 인출하는데 걸리는 시간을 저장하고 sort함수로 오른차 순으로 정렬해준다.

 

sort함수는 algorithm 헤더파일에 들어있다.

 

sort(arr,arr+n)의 의미는 sort(메모리 시작주소, 마지막 메모리 주소)를 의미하며 배열 처음부터 n개까지 오름차순으로 정렬을 해준다.

 

그리고 반복문을 돌면서 ans += arr[i]*(n-i)로 인출하는데 걸리는 시간의 최솟값의 합을 구해준다.

 

arr[i]에 n-i를 곱해준 이유는 ATM에서 줄을 서고 있는 사람들은 앞사람들이 걸리는 시간 + 자기 자신의 시간만큼 걸리게 된다.

 

첫 번째 사람은 뒷사람 n-1명에게 arr[0]만큼의 시간을 소요하게 만든다. 자기 자신이 걸리는 시간 + 뒷사람 n-1명에게 걸리는 시간이 소요되므로 arr[0] + arr[0]*(n-1) = arr[0]*n 만큼의 시간이 걸리게 된다.

 

두 번째 사람은 뒷사람 n-2명에게 arr[1]만큼의 시간을 소요하게 만든다. arr[1] + arr[1]*(n-2) = arr[1]*(n-1) 만큼의 시간이 소요된다.

 

n번째 사람은 자기 자신만 시간이 소요되므로 arr[n-1]만큼의 시간이 소요된다.

 

따라서 1 ~ n번째 사람이 걸리는 시간들을 다 더해주면 ans += arr[i]*(n-i) (i는 0부터 n-1까지) 가 된다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

오름자순으로 정렬을 해야 최솟값의 합을 구할 수 있다는 사실,

 

정렬함수 sort를 알고 있으면 쉽게 풀 수 있는 문제였다.