[백준][C++] 1758 알바생 강호

1758. 알바생 강호

1758번: 알바생 강호

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

문제는 정렬로 쉽게 풀 수 있었다.

 

등수가 올라갈수록 팁이 깎이는 가격이 늘어나므로 가장 큰 팁을 줄 손님의 팁을 보존해야 한다고 생각했다. 따라서 팁을 많이 줄 사람의 등수가 작야아하는 것이다.

 

처음엔 정렬 코드 그 한 줄을 쓰기 귀찮아서... multiset을 썼더니 시간 초과가 났다. next 함수 때문일 가능성도 있다.

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

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL);  cin.tie(NULL);

    multiset<int, greater<int>> tips;
    int len;
    long long int kanghoTip = 0;

    cin >> len;

    for (int i = 0; i < len; i++)
    {
        int input;
        cin >> input;
        tips.insert(input);
    }

    for (int i = 0; i < len; i++)
    {
        // 가장 큰 것부터
        int tip = *next(tips.begin(), i) - i;

        if (tip < 0) tip = 0;
        kanghoTip += tip;
    }

    cout << kanghoTip;
}

 

슬픈 마음으로 우선순위 큐로 구현을 해봤다.

#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL);  cin.tie(NULL);

    priority_queue<int> tips;

    //...

    for (int i = 0; i < len; i++)
    {
        int tip = tips.top() - i;
        tips.pop();

        if (tip < 0) tip = 0;
        kanghoTip += tip;
    }

    cout << kanghoTip;
}

이번에도 예제는 맞았지만, 결과는 틀렸습니다... 나는 이제야 내 알고리즘은 틀린 게 없다는 것을 알게 되었다.

 

틀린 이유는 자료형 때문...

N은 100,000보다 작거나 같은 자연수이다.
팁은 100,000보다 작거나 같은 자연수이다.

이 조건이라면 한계값으로 테스트했을 때 100000 * ((100000 - 0) + (100000 - 1) + + (100000 - 2)...) 형태로 나올 것이다. 그렇게 되면 얻는 팁이 int 범위를 넘어서게 되므로 long long int를 써주어야 하는 것이었다. 자료형을 늘려주니 바로 통과.

 

그리고 우선순위 큐를 쓰는 것보다 vector와 알고리즘 헤더의 sort 함수를 쓰는 게 더 빨라서 최종 제출은 vector로 했다.

    vector<int> tips;

    //...

    sort(tips.begin(), tips.end(), greater<int>());

    for (int i = 0; i < len; i++)
    {
        int tip = tips[i] - i;

        if (tip < 0) tip = 0;
        kanghoTip += tip;
    }

    cout << kanghoTip;

 

전체 코드

 

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

int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL);  cin.tie(NULL);

	vector<int> tips;
	int len;
	long long int kanghoTip = 0;

	tips.resize(100000);
	cin >> len;

	for (int i = 0; i < len; i++)
	{
		cin >> tips[i];
	}

	sort(tips.begin(), tips.end(), greater<int>());

	for (int i = 0; i < len; i++)
	{
		int tip = tips[i] - i;

		if (tip < 0) tip = 0;
		kanghoTip += tip;
	}

	cout << kanghoTip;
}

 

한계값을 정말로 테스트할 수는 없지만, 머릿속으로라도 테스트해서 내 코드의 결점을 발견하는 습관을 들여야겠다.