[그리디 #8] BOJ 1758 - 알바생 강호

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

1758번: 알바생 강호

 

접근 방법

그리디의 정석으로 풀 수 있는 문제 중 하나이다.

 

 이 문제에서 주문금액 - (등수 - 1)의 공식을 이용해 최고의 팁을 받는 것이 문제의 끝이다.

 

별다른 조건은 없기 때문에 주문금액이 가장 큰 손님부터 받게되면 팁을 최대로 챙길 수 있다.

 

쉽게 접근할 수 있는 문제라고 생각한다.

 

구현 시, N이 최대  100,000, 팁이 100,000을 넘을  수 있기 때문에 타입 선정에 주의하기만 하면된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 100001

int n;
vector<int> v;

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	
	sort(v.begin(), v.end(), cmp);


	
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] - i > 0) {
			sum += (v[i] - i);
		}
			
	}
	cout << sum;

}