글 읽기 - 최소힙을 구조체로 구현하였는데 틀린 부분을 못찾겠습니다 ㅠㅠ

skyde47 4년 전 0

구조체로 최소힙 구현하였는데 힙에 1부터 100만까지 역순으로 넣어서 테스트 해봤을때는 힙 자체는 순서대로 잘 나왔습니다만 문제에서 왜 자꾸 틀렸습니다를 뱉는지 모르겠습니다. ㅠㅠ 제 힙이 어디가 잘못됬는지 가르쳐 주시면 감사하겠습니다 ㅠㅠ

#include<stdio.h>

struct heap {
	int data[1000001];
	int s;
	void init() { s = 1; }
	void swap(int a, int b) { int tmp = data[a]; data[a] = data[b]; data[b] = tmp; }
	bool empty() { return s == 1; }
	int size() { return s; }
	void push(int a) {
		if (empty())data[s] = a;
		else {
			data[s] = a;
			for (int itr = s; itr > 1 && data[itr / 2] > data[itr]; itr /= 2)swap(itr, itr / 2);
		}
		s++;
	}
	int pop() {
		s--;
		int tmp = data[1];
		data[1] = data[s];
		for (int itr = 1; itr * 2 < s;) {
			int r = -1, l = -1;
			l = data[itr * 2];
			if (itr * 2 + 1 < s) r = data[itr * 2 + 1];
			if (r == -1 || l <= r) {
				if (l >= data[itr])break;
				swap(itr, itr * 2);
				itr *= 2;
			}
			else {
				if (r >= data[itr])break;
				swap(itr, itr * 2 + 1);
				itr * 2 + 1;
			}
		}
		return tmp;
	}
}h;

int n, b, c, sum;

int main() {
	scanf("%d", &n);
	h.init();
	for (int i = 0; i < n; i++) {
		scanf("%d", &b);
		h.push(b);
	}
	while (h.size() > 2) {
		b = h.pop();
		c = h.pop();
		h.push(b + c);
		sum += b + c;
	}
	printf("%d", sum);
}

seico75 4년 전 0

34 라인.

skyde47 4년 전 0

@seico75 아 소스가 잘못 첨부 되었네요 34번 라인은 수정했었습니다...글 수정하겠습니다!

#include<stdio.h>

struct heap {
	int data[1000001];
	int s;
	void init() { s = 1; }
	void swap(int a, int b) { int tmp = data[a]; data[a] = data[b]; data[b] = tmp; }
	bool empty() { return s == 1; }
	int size() { return s; }
	void push(int a) {
		if (empty())data[s] = a;
		else {
			data[s] = a;
			for (int itr = s; itr > 1 && data[itr / 2] > data[itr]; itr /= 2)swap(itr, itr / 2);
		}
		s++;
	}
	int pop() {
		s--;
		int tmp = data[1];
		data[1] = data[s];
		for (int itr = 1; itr * 2 < s;) {
			int r = -1, l = -1;
			l = data[itr * 2];
			if (itr * 2 + 1 < s) r = data[itr * 2 + 1];
			if (r == -1 || l <= r) {
				if (l >= data[itr])break;
				swap(itr, itr * 2);
				itr *= 2;
			}
			else {
				if (r >= data[itr])break;
				swap(itr, itr * 2 + 1);
				itr = itr * 2 + 1;
			}
		}
		return tmp;
	}
}h;

int n, b, c, sum;

int main() {
	scanf("%d", &n);
	h.init();
	for (int i = 0; i < n; i++) {
		scanf("%d", &b);
		h.push(b);
	}
	while (h.size() > 2) {
		b = h.pop();
		c = h.pop();
		h.push(b + c);
		sum += b + c;
	}
	printf("%d", sum);
}

seico75 4년 전 0

다시 주신 소스는 통과합니다.

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

문제

문제

출처

ICPC

최소힙을 구조체로 구현하였는데 틀린 부분을 못찾겠습니다 ㅠㅠ

skyde47 4년 전 0

seico75 4년 전 0

skyde47 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말