[Silver IV] ATM - 11399

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

그리디 알고리즘, 정렬

제출 일자

2024년 8월 20일 15:35:49

문제 설명

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 P_i분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P₁ = 3, P₂ = 1, P₃ = 4, P₄ = 3, P₅ = 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과 각 사람이 돈을 인출하는데 걸리는 시간 P_i가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 P_i가 주어진다. (1 ≤ P_i ≤ 1,000)

출력

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

제출코드

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

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N;
	cin >> N;

	int* ptrArr = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> ptrArr[i];
	}
	
	sort(ptrArr, ptrArr+N);
	int result = 0, tmp = 0;
	for (int i = 0; i < N; i++) {
		tmp += ptrArr[i];
		result += tmp;
	}
	cout << result << endl;
}

풀이

atm기에서 인출하는데 걸리는 시간의 최솟값을 구하려면 각각 걸리는 시간을 오름차순으로 정렬하여 모두 일련의 과정으로 더해주면 된다.

따라서 sort함수로 정렬하였고 앞사람이 걸린 시간을 저장하기 위해 tmp변수와 총 결괏값 저장을 위한 result 변수를 정의하여 해결하였다.

다른 풀이

변수를 하나만 쓰는 풀이가 있어서 가지고 왔다.

...
for(int i=0;i<n;i++)
	result += ptrArr[i]*(n-i);

위 식으로 대체가 가능하다. 기존의 코드에서는 더할때마다 저장해놓은 tmp변수를 합하여 for문을 진행하였다. 한사람 한사람 진행하는 느낌으로 말이다.

이 코드는 첫번째 사람으로 인해 딜레이 되는 시간을 모든 결괏값에 미리 더하는 식이다. 이를 테면, 첫번째 사람은 자기 자신과 뒷사람 n-1명에게 ptrArr[i]의 값만큼 딜레이를 시킨다. (자기 자신은 소요하는 것이지만,)

즉, 자기 자신과 뒷사람 n-1명에게 걸릴 시간을 미리 한번에 result에 더한다.

두번째 사람은 자기 자신과 뒷사람 n-2명에게 걸릴 시간을 미리 한번에 더한다. -> ptrArr[1] + ptrArr[1](n-2) = ptrArr[1](n-1)

그러므로 ptrArr[i]*(n-1) 을 매번 곱하여 구현하면 완료된다.