백준 1758 - 알바생강호(c++, Greedy)

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

1758번: 알바생 강호

 

 

문제 요약 

알바생 강호가 줄선 손님들에게 팁을 받는다. 각 손님은 원래 주려했던 팁 금액 -  (받은등수 -1) 만큼의 금액을

팁으로 준다. 위 식의 결과가 음수라면 강호는 그 손님에게 팁을 받을 수 없다. 

사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 잇는 팁의 최댓값을 구하는 프로그램을 작성하시오.

 

접근   

큰 팁을 주려는 손님이 후 순위로 밀려나서 차감되는 금액이 커지면 최댓값과 멀어지므로 내림차순으로 정렬 후 각각의 값에서 (받은등수 -1)만큼 빼고 음수가 아닐때만 sum값에 더해주면 최대값을 얻을 수 있을 것라고 접근했다.

 

코드 

#define _CRT_SECURE_NO_WARNINGS

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

//무조건 팁 큰사람 앞으로

int N; 
//int people[100001];
vector<int> people = {};

bool compare(int i, int j) {
	return i > j;
}
int main() {
	int x;
	long long sum = 0;

	cin >> N;

	for (int i = 0; i < N; i++) {
	
		cin >> x;
		people.push_back(x);
	}

	sort(people.begin(), people.end(), compare);


	for (int i = 0; i < N; i++) {
		
		if (people[i] - i > 0)
			sum += people[i] - i;
	}

	cout << sum;

	

	return 0;
}

 

풀이

팁을 많이 주는 사람이 뒤로갈수록 마이너스 되는 금액이 크고 팁을 적게주는 사람은 뒤로 가서 마이너스가 되더라도 팁이 음수가 되지 않기 때문에 내림차순으로 정렬 후 공식에서 음수가 아닌 값만 sum에 더했다. Greedy알고리즘으로 분류된다.

 

고찰

굉장히 쉬워보이는 문제지만 굉장히 쉽다. 접근방식은 옳았지만 하나 간과한 것이 있었다. 각 팁의 값이 100000이하의 자연수인데 그 값의 합을 받는 sum변수를 int로 선언하여 자료형의 범위를 초과했다. int형 변수의 범위는 –2,147,483,648 ~ 2,147,483,647 라는 것을 기억해두고 자료형의 크기를 신경쓰며 꼼꼼히 문제를 풀어야한다.