백준 알고리즘 중급 - 그리디 알고리즘 - 2

욕심쟁이 스머프

이번 챕터에서는 얻을 게 엄청 많았다. 특히 큰 수가 들어갈 때 항상 쩔쩔 맸는데,

전환점이 될 수도 있을 정도로 많은 것을 얻은 것 같다. 체크 해뒀다가 잘 써먹어보자.

이제 효율적인 공부 흐름을 어느정도 터득한 것 같다. 이 흐름대로 꾸준히 잘 해보자.

정리 시작!

-

* 보석 도둑 (high) : 보석 도둑이 훔칠 수 있는 최댓값을 구하는 문제다. 어려웠다. 

1202번: 보석 도둑

- 보석의 가격을 기준으로 한 풀이와 무게를 기준으로 한 풀이, 2가지의 해결법이 있다. 보석의 가격을 기준으로 할 때는 입력 받은 보석의 정보를 가격을 기준으로 내림차순 정렬하고, multiset과 lower_bound를 이용해서 가방에 넣어준다.

- 무게를 기준으로 할 때는 입력 받은 보석의 정보와 가방의 정보를 같이 정렬해준다. 무게를 기준으로 오름차순 정렬하고, 가방의 정보가 같은 무게의 가장 끝에 오도록 정렬해준다. priority queue를 이용해서 가방에 넣어준다.

- multiset은 set에 중복을 허용한 것이라고 생각하면 된다. 나머지는 set과 개념이 똑같다. priority queue는 heap 구조라고 보면 된다. 디폴트는 max heap이고, 설정을 해주면 min heap으로도 사용할 수 있다.

- multiset의 lower_bound 함수는 iterator 값을 리턴하므로 보통 auto로 처리해준다. multiset 안에서 지정한 수보다 같거나 큰 가장 작은 값의 위치를 포인팅한다.

- 먼저 보석 가격을 기준으로 multiset 과 lower_bound를 사용한 풀이다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct jw {
	int m, v;
};
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	vector<jw> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].m, &a[i].v);
	}
	sort(a.begin(), a.end(), [](jw u, jw v) {
		return u.v > v.v || (u.v == v.v && u.m < v.m);
	});

	multiset<int> s;
	for (int i = 0; i < k; i++) {
		int t;
		scanf("%d", &t);
		s.insert(t);
	}

	long long ans = 0;
	for (int i = 0; i < n; i++) {
		auto t = s.lower_bound(a[i].m);
		if (t != s.end()) {
			ans += (long long)a[i].v;
			s.erase(t);
		}
	}

	printf("%lld\n", ans);
	return 0;
}

- pair보다 구조체를 선언하는 것이 보기도 좋고 이해도 빠르다. 이번 문제를 통해 sort를 할 때 따로 함수를 선언하지 않고 인자 안에서 바로 값을 지정해주는 요령을 익혔다. 요긴하게 써먹자. 비싼 보석부터 정렬해준다. 

- lower bound 값이 s.end()와 같으면, s 내부에 해당하는 값이 없는 것이므로 s.end()가 아닐 때 해당 위치의 가격을 더해주고 erase 해준다. 이를 반복한다.

 

- 다음으로 넣어야 하는 가방을 기준으로 한 풀이다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct jw {
	int m, v, w;
};
int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	vector<jw> a(n+k);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].m, &a[i].v);
	}
	for (int i = 0; i < k; i++) {
		scanf("%d", &a[i + n].m);
		a[i + n].w = 1;
	}
	sort(a.begin(), a.end(), [](jw u, jw v) {
		return u.m < v.m || (u.m == v.m && u.w < v.w);
	});

	long long ans = 0;
	priority_queue<int> q;
	for (auto &p : a) {
		if (p.w == 0) {
			q.push(p.v);
		}
		else {
			if (!q.empty()) {
				ans += (long long)q.top();
				q.pop();
			}
		}
	}

	printf("%lld\n", ans);
	return 0;
}

- 보석 정보와 가방 정보를 같이 정렬해준다. 구조체 안의 w는 보석과 가방을 구별하는 역할을 한다.

- 무게를 기준으로 내림차순 정렬한다. 가방은 동일한 무게에서 가장 끝에 오도록 정렬해준다.

- priority queue(p.q)를 이용해서 값을 하나씩 넣어준다. w가 0이면 보석이므로 p.q에 넣어준다. 1일 때는 가방이므로, 지금까지 넣은 수 중에서 가장 큰 수를 더해주면 된다. p.q가 친절하게 정렬을 해줘서 가장 위에 큰 값이 와있다. + (auto &p와 같이 구조체를 활용하는 법도 잘 기억해뒀다가 요긴하게 써먹도록 하자.)

- 한 문제를 장황하게 설명했는데, 그만큼 얻어갈게 많은 문제였다. 앞으로 만날 문제들에서도 잘 활용해보자!

 

* 순회 강연 (mid) : 위의 보석 도둑 문제와 비슷한 문제다. 따지고 보면 조건만 살짝 다르다.

2109번: 순회강연

- 보석 도둑 문제는 가방의 무게 제한보다 같거나 작은 무게를 가진 보석을 선택하는 것이었다면, 순회강연 문제는 강연 가능한 범위 안에서 강연료를 최대로 받도록 하는 문제다. 비슷한 구조를 가졌기에 위의 방법대로 풀면 풀린다.

- 근데 multiset과 lower bound를 이용하기는 좀 애매하다. 몇 번 강의를 가는지 정해져 있지 않기 때문이다. 가능한 최대 일수를 구해 priority queue로 해결하는 것이 편할 것 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct lec {
	int p, d;
};
int main()
{
	int n;
	scanf("%d", &n);
	vector<lec> a(n);
	int lim = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].p, &a[i].d);
		lim = max(lim, a[i].d);
	}
	for (int i = 1; i <= lim; i++) {
		lec t;
		t.p = 0; t.d = i;
		a.push_back(t);
	}
	sort(a.begin(), a.end(), [](lec u, lec v) {
		return u.d > v.d || (u.d == v.d && u.p > v.p);
	});

	int ans = 0;
	priority_queue<int> q;
	for (auto &p : a) {
		if (p.p != 0) {
			q.push(p.p);
		}
		else {
			if (!q.empty()) {
				ans += q.top();
				q.pop();
			}
		}
	}

	printf("%d\n", ans);
	return 0;
}

- 강연 정보를 입력하면서 가능한 최대 일수를 구한다. 그만큼 같은 벡터에 p=0인 값으로 넣어준다. d를 내림차순으로 정렬하고, p도 내림차순으로 정렬해주면 구하려는 날의 값이 같은 d의 가장 마지막 값이 된다.

 

* 가장 긴 증가하는 부분 수열 3 (mid) : dp에서 만났던 문제다. 범위가 엄청 커서 dp로는 안 풀린다.

12738번: 가장 긴 증가하는 부분 수열 3

- lower_bound를 사용하면 쉽게 풀린다. 이제 LIS는 무조건 lower_bound만 생각하면 되겠다. 까먹지 말자 좀!

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	vector<int>a;
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		auto t = lower_bound(a.begin(), a.end(), num);
		if (t == a.end()) {
			a.push_back(num);
		}
		else {
			*t = num;
		}
	}
	printf("%d\n", a.size());
	return 0;
}

- 벡터에서도 lower_bound를 쓸 수 있다. 요령을 잘 익혀두자. end 값과 같다는 것은 벡터가 비어있거나, 가장 마지막 값이 lower_bound라는 뜻이다.

- 그렇지 않다면 lower_bound 위치를 가리키고 있을 것이므로, 그 주소값에 입력한 값을 넣는다.

-

multiset, lower_bound, priority queue 등 많은 것을 배운 챕터였다. 활용도가 아주 높을 것 같다.

한 단계 업그레이드 된 느낌도 들고.. 좋다. 아마 예전처럼 낑낑대면서 풀려고 했다가는 또 며칠 걸렸을 거다.

이 속도로 계속 가보자. 똑똑하게 공부하자 좀!

정리 끝!