시간초과

우선 순위 큐를 쓰는 대신에 보석을 넣는 벡터(J)에서 erase로 가방에 넣을 수 있는 보석은 바로 제거하는 알고리즘으로 작성하였는데 시간초과가 뜨네요.. erase를 사용해서 시간복잡도가 높아진 것일까요? 이런 방법으로는 문제를 풀 수 없을까요?

http://boj.kr/2136c28d9e844ba1b1d04a5e369dada0

또한 j를 초기화 할 때 for문 안에서 초기화 해야하는 것 아닌가요? 가방 크기가 작아 못 들어간 보석도 다시 처음부터 탐색해야하니까요. 근데 for 문안에서 j를 초기화 하면 메모리 초과가 뜨네용 ㅜㅜ

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, k, ret, temp1, temp;

int main(){

ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

cin >> n >> k;

vector<pair<ll,ll>> v(n);

vector<ll> vv(k);

for(int i = 0; i < n; i++){

cin >> v[i].first >> v[i].second;

}

for(int i = 0; i < k; i++) cin >> vv[i];

sort(v.begin(), v.end());

sort(vv.begin(), vv.end());

priority_queue<ll> pq;

// 여기 자리에 있던 int j = 0;를 아래로 옮겼습니다.

for(int i = 0; i < k; i++){

int j = 0;

while(j < n && v[j].first <= vv[i]) pq.push(v[j++].second);

if(pq.size()){

ret += pq.top(); pq.pop();

}

cout << ret << "\n";

return 0;

}

안녕하세요 효민님 ㅎㅎ

>> 우선순위큐를 쓰는 이유 등은 시간복잡도를 줄이기 위해서입니다.

해당 코드를 보시면 N * K인데 이는 30만 곱하기 30만입니다.

너무나 시간복잡도가 큽니다.

	for(int i : bag){
		for( int j=0; j<J.size(); j++){

가방 크기가 작아 못 들어간 보석도 다시 처음부터 탐색해야하니까요.

		while(j < n && v[j].first <= vv[i]) pq.push(v[j++].second);

이부분이죠?

이미 이전에 sort를 했기 때문에 무게가 더 커지는 순으로 정렬이 된 것은 자명합니다.

	sort(v.begin(), v.end());

앞의 while문의 의미는 담을 수 있는 것은 모두 담아둔다.

지금의 가방 허용무게로부터 무게가 허용한 보석들을 말이죠.

그리고...

		if(pq.size()){
			ret += pq.top(); pq.pop();
		}

이렇게 뺍니다. 그 중 가장 큰 것을 빼는데요.(가격이)

j가 만약 첫번째 가방으로도 다 ++이 연속으로 되어 모든 것을 담았고 n이 되어도 상관없습니다.

그 다음 가방은 반드시 그이전의 가방에서 담을 수 있는 모든 보석을 담을 수있다.

라는 명제가 자명하기 때문에(정렬을 했기 때문에) 다시 탐색해서 확인할 필요가 없습니다.

예를 들어

1 2 3 4 5 라는 보석이 있고 그걸 다 담았다면 pq에 처음에는 5를 ret += 를 합니다.

그리고 그 다음 4를 추출하게 되겠죠? 이렇게 정렬 + pq의 특성을 이용해서 다시 탐색할 필요없이 최적해를 찾게 되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변