[백준] 1758번 : 알바생 강호 (C언어 / C99)

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

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

 

 

조건 및 입출력

- 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

- 강호가 받을 수 있는 팁의 최댓값을 출력한다.

- 시간 제한: 2초 이내 / 메모리 제한: 256MB 이내

 

 

코드 (C99)

#include <stdio.h>

//프로토타입 선언부
void heap_sort(int heap[], int size);

//전역변수 선언부
int waiting[100000] = { 0 };

main()
{
	int test;
	long long result = 0;
	scanf("%d", &test);

	for (int i = 0; i < test; i++)
		scanf("%d", &waiting[i]);

	heap_sort(waiting, test); //오름차순 정렬

	for (int i = test - 1; i >= 0; i--)
	{
		if (waiting[i] - (test - i - 1) <= 0)
			continue;
		result += waiting[i] - (test - i - 1);
	}
	printf("%lld", result);

	return 0;
}

void heap_sort(int heap[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int child = i;
		do
		{
			int root = (child - 1) / 2;
			if (heap[root] < heap[child])
			{
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			child = root;
		} while (child != 0);
	}

	for (int i = size - 1; i >= 0; i--)
	{
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int child = 1;
		do
		{
			child = 2 * root + 1;

			if (child < i - 1 && heap[child] < heap[child + 1])
				child++;
			if (child < i && heap[root] < heap[child])
			{
				temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			root = child;
		} while (child < i);
	}
}

 

 

---

여담

정렬을 이용하여 문제를 풀이한다.

지금보니 내림차순 정렬을 하는 것이 문제 풀이 하는 것이 좋아보인다.

나는 이미 힙 정렬을 오름차순으로 만들어놔서, 오름차순 되어 있는 배열을 이용하였다.

 

가장 팁을 높게 주는 사람을 기준으로, 우선순위를 부여한다.

만약, 팁-(순위-1)를 했을 때 0이하이면 팁을 반영하지 않는다.

 

그렇게 하여 모든 사람의 경우를 체크하여 최대로 팁을 받을 수 있는 경우를 출력하면 된다.

다만, 조심해야 할 점은 최대 팁의 자료형은 int가 아닌, long long 이여야 한다.

 

나는 int 형으로 선언했다, 오답처리 되었다.

질문 게시판에 있는 글을 보고 int 형에서 long long으로 변경했더니 바로 정답 처리되었다.

 

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)