백준 11399번 ATM (python, c++)

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

11399번: ATM

위는 문제 링크입니다.

 

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 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분이 된다.

 

문제에 나온 예시를 보면 각 사람이 돈을 인출하는데 필요한 시간의 합을 구할 때 앞 순서의 값이 가장 많이 더해지는 걸 알 수 있다. 그러므로 앞에 있는 사람일수록 적은 시간이 걸리도록 해야 최소값을 구할 수 있다.

 

 

<python>

n=int(input())
arr = list(map(int, input().split()))
arr.sort()
min=0
for i in range(n):
    min += arr[i]*(n-i)
print(min)

 

 

<C++>

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

const int MAX = 1000;

int N;
int person[MAX];


int main(void) {

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> person[i];
	}
	sort(person, person + N);
	int min = 0;
	for (int i = 0; i < N; i++) {
			min += person[i]*(N-i);
	}
	cout << min;
	return 0;
}