글 읽기 - '틀렸습니다'가 계속 나오는데 반례 부탁드립니다 ㅜㅜ

java_java 1년 전 0

아직 제 수준의 문제가 아닌듯 하지만 풀고싶습니다!

push랑 pop은 혼자 구현할 줄 몰라 구글링 참고하였습니다.

보석 무게,가격은 qsort를 이용해 가격을 기준으로 내림차순 정렬하였고,

가방 무게는 push와 pop을 이용해 오름차순으로 정렬하였습니다.

보석 가격이 높은 순서대로, 해당 보석 무게를 가장 가벼운 가방 무게와 비교하여 계산하였습니다.

예제와 질문글의 반례를 입력해보았으나 답은 맞았습니다. push와 pop을 사용하기 전에는 시간초과가 나왔는데 시간초과를 해결하자니 계속 틀리네요 ㅠㅠ

답변 해주시면 감사하겠습니다!

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

#define MAX_SIZE  300000

int compare(const void* a, const void* b);

typedef struct JEWEL {
	int weight;
	int price;
}JEWEL;

typedef struct priorityQueue {
	int heap[MAX_SIZE];
	int count;
}priorityQueue;

void nodeChange(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

/********************************push 구현****************************************/
void push(priorityQueue* root, int data) {

	if (root->count >= MAX_SIZE) return;

	root->heap[root->count] = data;

	int now = root->count;
	int parent = (root->count - 1) / 2;

	while (now > 0 && root->heap[now] < root->heap[parent]) {
		nodeChange(&root->heap[now], &root->heap[parent]);
		now = parent;
		parent = (parent - 1) / 2;
	}
	root->count++;
}

/********************************pop 구현****************************************/
int pop(priorityQueue* root) {
	if (root->count <= 0) return -9999;

	int res = root->heap[0];

	root->count--;
	root->heap[0] = root->heap[root->count];

	int now = 0, leftChild = 1, rightChild = 2;
	int target = now;

	while (leftChild < root->count) {
		if (root->heap[target] < root->heap[leftChild]) target = leftChild;

		if (root->heap[target] < root->heap[rightChild] && rightChild > root->count) target = rightChild;

		if (target == now) break;
		else {
			nodeChange(&root->heap[now], &root->heap[target]);

			now = target;

			leftChild = now * 2 + 1;
			rightChild = now * 2 + 2;

		}
	}
	return res;
}
/********************************main 함수****************************************/
int main() {

	int n, k, cnt = 1;
	int c, tmp;
	long long sum =0;
	JEWEL* gem;
	priorityQueue root;
    
	root.count = 0;

	scanf("%d %d", &n, &k);

	gem = (JEWEL*)malloc(sizeof(JEWEL) * n);

	for (int i = 0; i < n; i++) 
		scanf("%d %d", &gem[i].weight, &gem[i].price);
	
	for (int i = 0; i < k; i++) {
		scanf("%d", &c);
		push(&root, c);
		// 가방 무게를 오름차순 정렬
	}

	// 보석 가격을 기준으로 내림차순 정렬
	qsort(gem, n, sizeof(JEWEL), compare);

	tmp = pop(&root);
	for (int i = 0; i < n; i++) {
		// 가격이 비싼 보석의 무게부터 가벼운 가방의 무게 비교
		if (gem[i].weight <= tmp) {
			sum += gem[i].price;
			if (cnt < k) { // pop한 횟수 
				tmp = pop(&root);
				cnt++;
			}
			else break;
		}

	}

	printf("%lld", sum);

	free(gem);

	return 0;
}

int compare(const void* a, const void* b) {
	JEWEL num1 = *(JEWEL*)a;
	JEWEL num2 = *(JEWEL*)b;

	if (num1.price < num2.price) return 1;
	if (num1.price > num2.price) return -1;
	return 0;
}

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

문제

문제

출처

ICPC

'틀렸습니다'가 계속 나오는데 반례 부탁드립니다 ㅜㅜ

java_java 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말