백준 1202 - 보석 도둑 (2가지 풀이)

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

그리디 알고리즘을 이용하는 문제. 두 가지 풀이 방법이 있다.

 

풀이 1 : multiset

그리디한 접근 방식은 다음과 같다. '비싼 보석을 최대한 작은 가방에 넣는다.'

 

- priority queue를 통해 가장 비싼 보석을 고른다.

- binary search를 통해 해당 보석을 담을 수 있는 가장 작은 가방을 고른다.

- 그러한 가방이 존재하면, 보석 무게의 총합을 갱신하고 그 가방을 방문 처리한다.

 

매번 가장 비싼 보석을 선택하기 위해 priority queue는 { 가격, 무게 }의 최대힙으로 설정한다.

 

그리고 방문 여부와 이분 탐색은 visited를 이용해 직접 구현하려 했으나... 생각보다 까다로워서 실패했다. 대신 같은 기능을 multiset을 사용해 쉽게 구현할 수 있다. 이분 탐색은 lower_bound로, 방문 처리는 선택한 가방을 erase하는 것으로 대체하면 된다.

 

여기서 주의!!!! 알고리즘 헤더파일에서 지원하는 lower_bound는 오름차순으로 정렬된 배열에서만 사용할 수 있는데, set은 인덱스 상으로 봤을 때 정렬되어있지 않다. 따라서 set에 함수 lower_bound를 쓰면 시간복잡도가 O(n)이 된다. 이 때는 set에 자체 내장된 메소드 set.lower_bound(val)를 써야 시간복잡도 O(log n)으로 수행할 수 있다.

 

주의 2!!!! multiset에서의 삭제는 erase 메소드를 사용하는데, 이때 parameter를 '삭제할 값'으로 하면 중복된 값이 모두 삭제된다. 현재 가방 1개만 삭제하려면 값 대신 반복자를 전달해야 한다.

 

1번 코드

//각 보석을 넣을 수 있는 가방 중 가장 작은 가방을 고른다

//가격, 무게
priority_queue<PII> pq;

//다른 배열에 저장하지 않고 우선순위 큐에 바로 넣어도 됨
for (int i = 0; i < N; i++) {
    int v, w;
    cin >> w >> v;
    pq.push({ v, w });
}

multiset<int> MS;

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

ll res = 0;
while (!pq.empty()) {

    //가장 비싼 보석
    PII cur(pq.top());
    int v = cur.first, w = cur.second;
    pq.pop();

    //넣을 수 있는 가장 작은 가방, 메소드 lower_bound 사용
    multiset<int>::iterator iter = MS.lower_bound(w);

	//존재할 경우
    if (iter != MS.end()) {
        res += v;
        
        //값 대신 반복자로 삭제
        MS.erase(iter);
    }
	
    //더 이상 넣을 가방이 없을 경우
    if (MS.empty()) break;
}

cout << res << endl;

 

풀이 2 : priority queue

 

1번 풀이에서도 우선순위 큐는 썼지만 그 용도가 다르다.

그리디한 접근 방식은 다음과 같다. '작은 가방에 최대한 비싼 보석을 넣는다.'

 

- 보석과 가방을 모두 무게 기준 오름차순 정렬한다.

- 정렬한 가방에 대해, 현재 가방에 담을 수 있는 보석을 모두 priority queue에 넣는다. 여기서의 priority queue는 '가격' 하나만 기준으로 삼는 최대 힙이다.

- 현재 priority queue의 맨 위에는 현재까지 넣을 수 있는 보석들 중 가장 비싼 가격의 보석이 들어있다. 그 보석만 선택해 총합을 갱신한다.

 

i번째 가방에서 priority queue에 넣은 보석은 i+1번째 가방에도 넣을 수 있다. 따라서 값비싼 보석이 앞부분에 몰려있어도 걱정할 필요가 없다. 아래 TC를 보자.

3 3
1 100
2 200
3 300
4 10
5 20
3
4
5

이 알고리즘을 적용하면 2번 가방에서는 10달러, 3번 가방에서는 20달러 보석밖에 챙길 게 없지만, 1번 가방에서 챙길 수 있던 더 비싼 200달러, 100달러짜리 보석을 두 가방에 넣게 된다.

 

2번 코드

//각 가방에 넣을 수 있는 보석 중 가장 비싼 보석을 고른다

int N, K;
cin >> N >> K;
vector<PII> J(N);

for (int i = 0; i < N; i++)
    cin >> J[i].first >> J[i].second;

//무게 기준 오름차순
sort(J.begin(), J.end());

vector<int> B(K);
for (int i = 0; i < K; i++)
    cin >> B[i];

//무게 기준 오름차순
sort(B.begin(), B.end());

//가격 기준 최대 힙
priority_queue<int> pq;

ll res = 0;
int idx = 0;
for (int i = 0; i < K; i++) {

	//i번째 가방에 넣을 수 있는 보석은 모두 선택
    while (idx < N && J[idx].first <= B[i])
    	//가격을 최대 힙에 삽입
        pq.push(J[idx++].second);

    if (!pq.empty()) {
    	//가장 비싼 보석 하나만 선택
        res += pq.top();
        pq.pop();
    }
}

cout << res << endl;

 

참고로 결과값을 int 자료형으로 설정하면 오버플로우가 발생하니 long long으로 해야한다.