글 읽기 - 이런 방법으로 풀면 왜 시간초과가 나는건가요?

wnsgur1595 4년 전 0

다음과 같은 방법으로 maxheap에 bound가 가장 큰 것부터 정렬하고, 하나씩 꺼내오면서 Max가 될 수 있는지 확인하고, 끝까지 돌렸을때, 그때의 Max값을 출력하는 프로그램입니다. 제 생각으로는, 이 프로그램에서 bound값을 알아내기 위해서 여러번 반복하는 행위 때문에 시간초과가 뜨는 것같은데, 어떻게 해야 시간초과가 안뜰 수 있을까요?

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

struct Node {
	double bound = 0;
	long long w;
	long long s;
	int level;
};

struct Candy {
	long long w;
	long long s;
	double s_w;
};

struct cmp1 {
	bool operator()(Node* t, Node* u) {
		return t->bound < u->bound;
	}
};

bool cmp(Candy t, Candy u) {
	return t.s_w > u.s_w;
}

vector<Candy> arr1;
priority_queue<Node*, vector<Node*>, cmp1> pq1;
int N, W;
double Max = 0;

int func() {
	Node* start = new Node;
	int tmp = 0;
	int t = 0;
	while (tmp != W) {
		if (arr1[t].w + tmp <= W) {
			tmp += arr1[t].w;
			start->bound += arr1[t].s;
		}
		else {
			start->bound += (arr1[t].s_w * (W - tmp));
			tmp += (W - tmp);
		}
		t++;
	}
	start->w = 0;
	start->s = 0;
	start->level = 0;
	pq1.push(start);


	while (!pq1.empty()) {
		Node* temp = pq1.top();
		pq1.pop();
		if (Max > temp->bound) return Max;
		Node* temp2 = new Node;
		if (arr1[temp->level].w + temp->w <= W && Max < arr1[temp->level].s + temp->s) {
			Max = arr1[temp->level].s + temp->s;
		}
		if (arr1[temp->level].w + temp->w < W) {
			temp2->w = temp->w + arr1[temp->level].w;
			temp2->s = temp->s + arr1[temp->level].s;
			temp2->bound = temp->bound;
			temp2->level = temp->level + 1;
			if (temp2->bound > Max) {
				pq1.push(temp2);
			}
		}

		temp2 = new Node;
		temp2->w = temp->w;
		temp2->s = temp->s;
		temp2->level = temp->level + 1;
		temp2->bound = temp->s;
		int tmp2 = temp2->w;
		int t2 = temp2->level;
		while (tmp2 != W) {
			if (arr1[t2].w + tmp2 <= W) {
				tmp2 += arr1[t2].w;
				temp2->bound += arr1[t2].s;
			}
			else {
				temp2->bound += (arr1[t2].s_w * (W - tmp2));
				tmp2 += (W - tmp2);
			}
			t2++;
		}
		if (temp2->bound > Max) {
			pq1.push(temp2);
		}

	}
	return Max;
}

int main() {
	cin >> N >> W;
	for (int i = 0; i < N; i++) {
		Candy temp;
		cin >> temp.w >> temp.s;
		temp.s_w = (double)temp.s / (double)temp.w;
		arr1.push_back(temp);
	}
	sort(arr1.begin(), arr1.end(), cmp);
	
	cout << func() << endl;

	return 0;
}

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

문제

문제

출처

ICPC

이런 방법으로 풀면 왜 시간초과가 나는건가요?

wnsgur1595 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말