[백준/C++] 보석 도둑

1202번: 보석 도둑

[문제]

 

보석 N개를 상덕이의 가방(무게가 정해져 있는) K개에 넣었을 때 최대 가격을 구하기.

 

[풀이 과정]

우선, 이 문제가 가방의 무게, 보석의 무게와 가치 이렇게 입력을 받고

가방 무게에 따라 넣을 수 있는게 다르기 때문에 정렬을 해야겠다고 생각했다. 

 

일단, 처음에는 문제만 대충 보고 냅색 알고리즘인 줄 알았다. 근데 좀 생각해보면 안된다는 걸 알 수 있다.

=> DP로 풀기엔 메모리공간이나 시간 제약에 걸린다.

완탐으로 풀게 될 경우에는 N과 K의 최대가 3만이기 때문에 30만*30만 해서 안된다는 것도 알 수 있음. (1초 초과)

 

그 다음으로, 가방을 하나씩 돌면서넣을 수 있는 보석을 모두 하나씩 대입해본다 했을 때..

가방의 무게가 늘어날 수록 확인해봐야 하는 보석의 개수가 늘어나는데 이걸 매번 반복문으로 돌려주는게 완전 탐색이고

이 경우 시간이 안되기 때문에 한번에 할 수 있는 방법을 생각해야 했다. 

=> priority_queue를 사용하면 가능한 무게 중 가치가 제일 높은 보석을 골라내기 쉬울 거라 생각..

 

 

1. 정렬을 해준다 ( 오름차순 ) 

vector<pair<int, int>> jewelry; // 무게, 가치.

 

2. pq를 만들고, pq에 내 무게 이하의 보석들을 넣어준다. => priority_queue<int> pq

=> 무게는 낮기만 하면 상관 없기 때문에 가치만 넣어준다. 

 

// i는 가방

for(int i = 0; i < 가방 개수; i++){

    while(남아있는 보석이 있으면){

        if(보석의 무게가 현재 가방(i)보다 높으면) break;

        else pq에 보석의 가치를 넣는다.

    }

    // 위의 while문이 종료되었을 때,

    if(pq에 보석이 존재)

        정답에 가장 높은 가치의 보석을 꺼내어 넣는다

}

 

 

[코드]

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

using namespace std;

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

vector<pair<int, int>> jewelry;//보석 무게, 가치
vector<int> bag;


int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int M, V; // 무게, 가격
		cin >> M >> V;
		jewelry.push_back({ M,V });
	}

	for (int i = 0; i < K; i++) {
		int C; // 가방 무게
		cin >> C;
		bag.push_back(C);
	}

	sort(jewelry.begin(), jewelry.end());
	sort(bag.begin(), bag.end());


	priority_queue<int> pq;

	int num = 0;
	long long sum = 0;

	for (int i = 0; i < K; i++) {
		while (num < jewelry.size()) {
			if (jewelry[num].first > bag[i]) break;
			pq.push(jewelry[num].second);
			num++;
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}

	cout << sum;

}

 

[고찰]

다 괜찮았는데 2%? 3%? 에서 틀렸습니다...

정답을 int 형으로 썼을 때, 정답이 범위를 넘어버리는 상황이 발생했다. 

최대 무게가 1억임..;; 1억에 30만 곱한다고 하면 int 자료형의 범위를 넘어버리는 것. long long을 사용하니까 되긴 했다.

 

여지껏 int 자료형 범위를 한번도 고려해가면서 문제를 푼 적이 없는데 한 20억쯤 된다는 것...