#문제
11399번: ATM
https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
#접근방법
정렬을 하고 반복문을 돌면서 시간의 합을 구하면 된다.
#풀이
#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를 알고 있으면 쉽게 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 17626번 : Four Squares [C/C++] (0) | 2022.06.23 |
---|---|
[백준] 17219번 : 비밀번호 찾기 [C/C++] (0) | 2022.06.22 |
[백준] 11047번 : 동전 0 [C/C++] (0) | 2022.06.20 |
[백준] 1764번 : 듣보잡 [C/C++] (0) | 2022.06.19 |
[백준] 11723번 : 집합 [C/C++] (0) | 2022.06.18 |