나의, 코딩 일기

문제

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

스타박스에서는 손님을 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으로 변경했더니 바로 정답 처리되었다.