글 읽기 - 도와주세요 ㅠㅠ

ljb0967 11일 전 0

힙을 이용해서 우선 순위 큐를 구현해 보았는데요. 거의 모든 테스트 케이스를 넣었을 때 맞게 나오나 제출하면 바로 틀렸습니다 가 떠요.. 도대체 어디가 문제인 걸 까요??

#pragma warning(disable:4996)
#include <stdio.h>

typedef struct {
	long long int heap[1000];
	int count;
} PriorityQueue;

void swap(long long int* a, long long int* b) {
	long long int tmp = *a;
	*a = *b;
	*b = tmp;
}

void push(PriorityQueue* pq, long long int data) {
	if (pq->count >= 1000) return;
	int now = pq->count;
	pq->heap[now] = data;
	int parent = (now - 1) / 2;

	while (now > 0 && pq->heap[now] < pq->heap[parent]) {
		swap(&pq->heap[now], &pq->heap[parent]);
		now = parent;
		parent = (now - 1) / 2;
	}

	pq->count++;
}

int pop(PriorityQueue* pq) {
	if (pq->count <= 0) return -1;
	long long int res = pq->heap[0];
	pq->count--;
	pq->heap[0] = pq->heap[pq->count];
	int now = 0, left = 1, right = 2;

	while (now <= pq->count) {
		int change = now;
		if (left <= pq->count && pq->heap[now] > pq->heap[left]) change = left;
		if (right <= pq->count && pq->heap[now] > pq->heap[right] && pq->heap[left] > pq->heap[right]) change = right;
		if (change == now) break;										//코드 추가한 부분

		swap(&pq->heap[now], &pq->heap[change]);
		now = change;
		left = now * 2 + 1;
		right = now * 2 + 2;
	}

	return res;
}

int main(void) {
	PriorityQueue pq;
	pq.count = 0;
	
	int N; long long int card = 0;
	scanf("%d", &N);
	if (N == 1) {
		scanf("%lld", &card);
		printf("0");
		return 0;
	}
	else {
		for (int i = 0; i < N; i++) {
			int num = 0;
			scanf("%d", &num);
			push(&pq, num);
		}
		for (int i = 0; i < N - 1; i++) {
			long long int add = 0;
			add = pop(&pq) + pop(&pq);
			card += add;
			push(&pq, add);
		}
		printf("%lld", card);
	}
	return 0;
}

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

문제

문제

출처

ICPC

도와주세요 ㅠㅠ

ljb0967 11일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말