글 읽기 - 시간초과 질문있습니다..

tlqckd0 3년 전 0

시간초과가 왜 발생했는지 모르겠습니다.

보석의경우 vector<pair<int,int>> 로 지정해서 높은 가치순 -> 가벼운 순으로 하고

가방의 경우 multiset<int>를 사용하였고,

보석을 기준으로 들어갈수 있는 가방을 lower_bound로 찾고 가방을 지우는 방식으로 진행했습니다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int N,K;
vector<pair<int,int>> jewel;
multiset<int> bag;

bool compareJewel(pair<int, int> a, pair<int, int> b) { // 가치가 높은거 순으로 정렬 -> 가치가 같으면 가벼운순으로
	if (a.second == b.second) {
		return a.first < b.first;
	}
	else {
		return a.second > b.second;
	}
}
bool compareBag(int a, int b) { //가방은 용량이 큰 순으로
	return a > b;
}

int main(void) {

	//조건 입력
	cin >> N>>K;
	for (int i = 0; i < N; i++) {
		int weight, value;
		cin >> weight >> value;
		jewel.push_back(make_pair(weight, value));
	}
	for (int i = 0; i < K; i++) {
		int weight;
		cin >> weight;
		bag.insert(weight);
	}
	//정렬
	sort(jewel.begin(), jewel.end(), compareJewel);

	
	//가방에 뭐 넣을지 결정하기.. (비싸고 -> 가벼운 순으로)
	unsigned long long result = 0;
	int bound = 0;
	int restBagNum = (int)bag.size();
	for (int i = 0; i < N; i++) {
		bound = jewel[i].first;
		auto it = lower_bound(bag.begin(), bag.end(), bound);
		if (it != bag.end()) {
			result += jewel[i].second;
			bag.erase(it);
			restBagNum--;
		}
		if (restBagNum == 0)
			break;
	}

	cout << result << endl;

	return 0;
}

djm03178 3년 전 2

set이나 map 등의 자료구조에서 로그 시간에 동작하는 효율적인 lower_bound를 사용하려면 bag.lower_bound와 같이 멤버 함수로 있는 것을 사용해야 합니다. std::lower_bound의 인자로 넘기는 것은 O(N)의 시간이 걸립니다.

tlqckd0 3년 전 0

아! 감사합니다!! 해결됬어요 !! 라이브러리를 잘 알지도 못하고 사용했던것이 문제였네요ㅜㅜ

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

문제

문제

출처

ICPC

시간초과 질문있습니다..

tlqckd0 3년 전 0

djm03178 3년 전 2

tlqckd0 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말