글 읽기 - 보석문제 시간초과 원인을 알 수 있을까요?

choyj1127 1년 전 0

long long 으로는 해결이 되지않았고

시간초과라면 36번째 줄에서 원하는 위치를 pop하고 그것을 제외한 나머지를 다시 우선순위 큐에 insert함으로써 정렬된 우선순위큐가 완성시켰는데 이 과정이 원인일까..싶고, 그렇다면 어떤 방법으로 구현해야할지 조언 부탁드립니다

#include <stdio.h>
#include <stdlib.h>
typedef struct {
	long long int weight;
	long long int price;
}Heap;
Heap heap[300000];
Heap tmp[300000];
long long int heapCnt = 0;
long long int C[300000];
void swap(Heap* a, Heap* b) {
	Heap tmp = *a;
	*a = *b;
	*b = tmp;
}
void heapInit() {
	heapCnt = 0;
}
void push(long long int w, long long int p) {
	heap[heapCnt + 1].weight = w;
	heap[heapCnt + 1].price = p;
	heapCnt++;

	long long int child = heapCnt;
	long long int parent = child / 2;
	//price기준 maxheap
	while (child != 1 && heap[child].price > heap[parent].price) {
		swap(&heap[child], &heap[parent]);
		child = parent;
		parent = child / 2;
	}
}
long long int peekWeight(long long int cur) {
	return heap[cur].weight;
}
long long int popPrice(long long int cur) {
	long long int ret = heap[cur].price;

	long long int idx = 0;
	for (long long int i = 1; i < cur; i++)
		tmp[idx++] = heap[i];
	for (long long int i = cur + 1; i <= heapCnt; i++)
		tmp[idx++] = heap[i];
	heapCnt--;

	heapInit();
	for (long long int i = 0; i < idx; i++)
		push(tmp[i].weight, tmp[i].price);

	return ret;
}
int compare(const void* a, const void* b) {
	return *(long long int*)a - *(long long int*)b;
}
int main() {
	long long int N, K, m, v;
	scanf_s("%lld %lld", &N, &K);
	for (long long int i = 0; i < N; i++) {
		scanf_s("%lld %lld", &m, &v);
		push(m, v);
	}
	for (long long int i = 0; i < K; i++)
		scanf_s("%lld", &C[i]);

	qsort(C, K, sizeof(long long int), compare);

	long long int maxValue = 0;
	for (long long int i = 0; i < K; i++) {
		long long int bagWeight = C[i];
		long long int cur = 1;
		for (long long int j = 0; j < heapCnt; j++) {
			if (peekWeight(cur) <= bagWeight) 
				break;
			cur++;
		}

		maxValue += popPrice(cur);
	}

	/*
	1. 최대힙 구현
	2. 가방 C 오름차순 정렬
	3. 최대힙 내부 탐색하다가 가능한 무게가 나오면 바로 빼자
	*/
	printf("%lld", maxValue);
	return 0;
}

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

문제

문제

출처

ICPC

보석문제 시간초과 원인을 알 수 있을까요?

choyj1127 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말