시간초과

Question

우선 순위 큐를 쓰는 대신에 보석을 넣는 벡터(J)에서 erase로 가방에 넣을 수 있는 보석은 바로 제거하는 알고리즘으로 작성하였는데 시간초과가 뜨네요.. erase를 사용해서 시간복잡도가 높아진 것일까요? 이런 방법으로는 문제를 풀 수 없을까요? http://boj.kr/2136c28d9e844ba1b1d04a5e369dada0 또한 j를 초기화 할 때 for문 안에서 초기화 해야하는 것 아닌가요? 가방 크기가 작아 못 들어간 보석도 다시 처음부터 탐색해야하니까요. 근데 for 문안에서 j를 초기화 하면 메모리 초과가 뜨네용 ㅜㅜ #include 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> v(n); vector 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 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 << " "; return 0; }

큰돌 · Answer

안녕하세요 효민님 ㅎㅎ 우선 순위 큐를 쓰는 대신에 보석을 넣는 벡터(J)에서 erase로 가방에 넣을 수 있는 보석은 바로 제거하는 알고리즘으로 작성하였는데 시간초과가 뜨네요.. erase를 사용해서 시간복잡도가 높아진 것일까요? 이런 방법으로는 문제를 풀 수 없을까요? >> 우선순위큐를 쓰는 이유 등은 시간복잡도를 줄이기 위해서입니다. 해당 코드를 보시면 N * K인데 이는 30만 곱하기 30만입니다. 너무나 시간복잡도가 큽니다. for(int i : bag){ for( int j=0; 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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.