글 읽기 - 시간을 어떻게 하면 줄일 수 있을까요ㅠㅠ

051ssaa 3년 전 0

multimap과 lower_bound를 이용하였고

담을 수 있는 무게가 낮은 가방부터 그 무게 이하인 보석 중 가장 높은 가치의 보석을 담게 구현하였습니다..!

하지만 7%에서 자꾸 시간 초과가 뜨네요... 어떻게 하면 개선시킬 수 있을까요?? 도와주세요ㅠㅠㅠ!!!

#include <iostream>
#include <map>
#include <set>
using namespace std;

int main() { 
	multimap <int, int> gem;  // 보석의 가치와 무게 = 보석 목록, 오름차순
	multimap <int, int>::iterator g_iter;

	map <int, int, greater<int>> num; // 보석 가치 별 개수 = 개수 목록, 내림차순
	map <int, int>::iterator n_iter;

	multiset <int> bag;  // 가방, 오름차순
	multiset <int>::iterator b_iter;

	int N, K; cin >> N >> K;  // 보석의 개수, 가방의 개수

	for (int i = 0; i < N; i++) {
		int m, v; cin >> m >> v;
		gem.insert(make_pair(v, m));  // 보석의 가치가 key
		num[v]++;  // 가치 별 개수도 증가
	}

	for (int i = 0; i < K; i++) {
		int vol; cin >> vol;
		bag.insert(vol); 
	}

	long long sum = 0;
	for (b_iter = bag.begin(); b_iter != bag.end(); b_iter++) {
		n_iter = num.begin();
		g_iter = gem.lower_bound(n_iter->first);

		for ( ; ; ) {
			if (g_iter->second <= *b_iter) {  // 가방에 담을 수 있는 무게보다 보석 무게가 작거나 같다면
				sum += g_iter->first;  // 담는다
				num[g_iter->first]--;  // 개수는 하나 감소한다
				if (num[g_iter->first] == 0) num.erase(g_iter->first);  // 개수가 0이라면 개수 목록에서 지운다
				gem.erase(g_iter);  // 보석 목록에서도 담은 보석을 지워버린다
				break;
			}
			else {
				n_iter++;  // 다음 최대가치를 찾는다
				if (n_iter == num.end()) break;  // 다음 최대가치가 없다면 담을 수 있는 보석 없으므로 탈출
				g_iter = gem.lower_bound(n_iter->first);
			}
		}
	}
	cout << sum;
}

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

문제

문제

출처

ICPC

시간을 어떻게 하면 줄일 수 있을까요ㅠㅠ

051ssaa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말