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

✏️ 문제 링크

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

11399번: ATM

 

 

✏️ 문제 설명

 

✏️ 문제 풀이

 N이 1000이하이므로 O(n^2)의 삽입 정렬을 이용해도 무방 ※

인출 시간이 가장 적게 걸리는 사람이 가장 먼저 인출할 수 있도록 순서를 정하기(그리디 방식)

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int>A(N, 0);
	vector<int>S(N, 0);

	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int i = 1; i< N; i++) {
		int point = i;
		int value = A[i];
		
		for (int j = i - 1; j >= 0; j--) {
			if (A[i] > A[j]) {
				point = j + 1;
				break;
			}
			if (j == 0)
				point = 0;
		}
		for (int j = i; j > point; j--) {
			A[j] = A[j - 1];
		}
		A[point] = value;
	}

	S[0] = A[0];

	for (int i = 1; i < N; i++) {
		S[i] = S[i - 1] + A[i];
	}

	int sum = 0;

	for (int i = 0; i < N; i++)
		sum += S[i];

	cout << sum;
}