Greedy Problem in BOJ

Greedy 문제만 몇 개 풀었는데 어쩜 이렇게 실력이 쓰레기같은지 하나 풀 때마다 턱턱 막혀서 화가 너무난다. 그래서 살짝 문제 몇개를 정리 해보려 한다. 아오...

[BOJ] #8980 택배

풀이

가장 많이 고민한 그리디 문제 중 하나다. 다들 어떻게 이런 생각을 금방금방 해내는지 모르겠다

트럭에 실을 수 있는 최대 용량 C와 각각 마을에 있는 짐의 무게와 그 짐의 도착지가 주어진다.

이 문제는 왜 그리디일까? 한 번 방문한 도시를 다시 방문하지 않기 때문이다. 1번 도시부터 출발하여 오름차순으로 도시들을 방문한다. 따라서 다음과 같은 알고리즘을 적용할 수 있다.

1. 옮겨야 할 박스의 정보를 도착 도시를 기준으로 오름차순으로 정렬한다.
2. 정렬한 정보들 중 i번째 정보를 볼 때, i번째 짐의 시작도시부터 도착도시까지 각 도시에서 옮길 수 있는 박스의 양 (rem배열) 중 최대 값을 구한다.
3. C - 2번에서 구한 박스의 양과 i번째 정보의 짐의 양 중 더 작은 값을 구한다.
4. 3번에서 구한값만큼 더 옮길 수 있다! -> 답에 더해준다.
5. i번째 정보의 시작 ~ 도착 도시의 rem 배열을 갱신해준다.

쓰니까 조금 복잡한데 결국 앞에서부터 차례대로 보면서 옮길 수 있는 최대 양을 더해주는 것이다. 헷갈리고 아이디어 내는데 도움도 많이 받았으니 오래오래 기억하고 싶다 ㅠㅜ

 

Code

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair< pair<int,int>,int> pii;
vector<pii>ord;
int rem[2003];
int main() {
	int N, C,M;
	scanf("%d %d %d", &N, &C,&M);
	for (int i = 0; i < M; i++) {
		int s, g, num;
		scanf("%d %d %d", &s, &g, &num);
		ord.push_back({ {g,s},num });
	}
	sort(ord.begin(), ord.end() );
	int ans = 0;
	for (int i = 0; i < ord.size(); i++) {
		int send = ord[i].first.second, dest = ord[i].first.first, cost = ord[i].second;
		int maxi = 0;
		for (int j = send; j < dest; j++) {
			maxi = max(maxi, rem[j]);
		}
		maxi = min(cost, C - maxi);
		ans += maxi;
		for (int j = send; j < dest; j++) {
			rem[j] += maxi;
		}
	}
	printf("%d\n", ans);
	
}

[BOJ] #2812 크게 만들기

풀이

리얼 개뻘짓했다. 와 진짜 나 자신이 너무 빠가라 욕나올 뻔...

맨 처음엔 리얼 이중포문 돌렸다 ㅠㅜㅜ K개를 빼야하니까 0번째부터 K-1번째까지 중 제일 큰 수를 뽑고, 다시 그 수 부터 K-2개의 숫자 중 가장 큰 수를 뽑아 출력해주었다. 근데 비교를 이중 for문으로 해주었다!!! 리얼 개빠가 ㅠㅜ deque를 이용해서 내 앞의 숫자들이 나보다 작다면 pop_back해주고 나를 push_back해준다. 그리고 K번째부터 N-1번째 숫자를 넣을 땐 front를 출력해주고 pop_front를 해준다. 매번 앞의 K 개 중에서 가장 큰 숫자를 찾아준다고 생각하면 편하다.

이렇게 하면 O(n)만에 해결할 수 있다! 리얼 왜 이런 건 생각을 못할까ㅜㅜ

Code

#include <stdio.h>
#include <queue>
using namespace std;
int arr[500003];
deque<int>q;
int main() {
	int N, K,a;
	scanf("%d %d", &N, &K);
	int idx = 0,j;
	for (int i = 0; i < N; i++) {
		scanf("%1d", &a);
		while (!q.empty() && q.back() < a)q.pop_back();
		q.push_back(a);
		if (i >= K) {
			printf("%d", q.front());
			q.pop_front();
		}
	}
	return 0;


}