글 읽기 - 오류를 알고 싶습니다.

adfsfsf 2년 전 0

C언어로 우선순위 큐를 구현해서 시도했습니다. 자꾸 틀렸습니다 만 뜨네요. 반례나 오류를 알고 싶습니다.

#include <stdio.h>
#include <stdlib.h>

void push(long int num, long int nums[]);
long int pop(long int nums[]);

long int queueSize;

int main(void)
{
	long int N;
	long int sum = 0;
	long int tmp;
	long int i, j;
	long int num;
	long int nums[100005] = { 0 };

	scanf("%ld", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%ld", &num);
		push(num, nums);
	}
	while (queueSize > 1)
	{
		tmp = pop(nums);
		tmp = tmp + pop(nums);
		sum = sum + tmp;
		push(tmp, nums);
	}
	//값들을 우선순위 큐에 넣고 가장 작은 2개의 수를 pop한다. 그리고 그 합을 push한다. 크기가 1이 되면 종료
	printf("%ld\n", sum);
	return 0;
}

void push(long int num, long int nums[])
{
	long int last;
	long int tmp;

	if (queueSize == 0)
		nums[1] = num;
	else
	{
		last = queueSize + 1;
		tmp = last / 2;
		while (tmp > 0)
		{
			if (nums[tmp] > num)
			{
				nums[last] = nums[tmp];
				last = tmp;
				tmp = tmp / 2;
			}
			else break;
		}
		nums[last] = num;
	}
	queueSize++;
	return;
}

long int pop(long int nums[])
{
	long int last = 1;
	long int num = nums[1];
	long int check = nums[queueSize];
	long int tmp1 = 2;
	long int tmp2 = 3;
	long int tmp = last;

	if (queueSize > 1)
	{
		while (tmp1 < queueSize)
		{
			if (tmp2 >= queueSize)
			{
				if (nums[tmp1] < check)
					tmp = tmp1;
			}
			else
			{
				if (nums[tmp1] <= nums[tmp2])
					tmp = tmp1;
				else
					tmp = tmp2;
			}
			if (tmp == last)
				break;
			else
			{
				nums[last] = nums[tmp];
				last = tmp;
				tmp1 = last * 2;
				tmp2 = tmp1 + 1;
			}
		}
		nums[last] = check;
	}
	queueSize--;
	return num;
}

euphoric_n 2년 전 1

반례 드립니다.

input

20
224
653
518
407
195
811
821
589
678
738
530
301
714
304
588
669
219
318
442
866

output

44816

answer

44722

pop 함수를 다시 살펴보시기 바랍니다.

adfsfsf 2년 전 0

아, 또 전이랑 같은 실수를 해버렸네요... 83~86번 줄에서 tmp를 check와 값을 비교하지 않고 변경했네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

오류를 알고 싶습니다.

adfsfsf 2년 전 0

euphoric_n 2년 전 1

adfsfsf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말