[백준 17305] 사탕 배달 (C++)

문제 링크: https://www.acmicpc.net/problem/17305

17305번: 사탕 배달

1. 주의할 점

- 최대 25만개의 데이터로 인해 Knapsack 알고리즘은 불가능하다

- 가중치/ 무게의 비율 즉, 그리디로 할 경우 통과하지 못하는 경우도 있다

 

2. 구현

[첫 번째 시도 - 그리디]

- 가중치/무게의 비율이 높은 순으로 정렬 + 가중치가 같은 경우 무게가 낮은것이 앞으로 오도록 정렬

예외 케이스) 수납공간 5의 가방, (무게 3,당도 4), (무게 5, 당도 5)가 있을 경우, 실제 답이 5지만, 4를 출력한다.

 

[두 번째 시도 - Knapsack]

- 2차 배열의 DP를 만들어야하지만 N의 최대인 경우 메모리초과 발생 예상 -> 포기

 

[세 번째 시도 - 정렬 + 간단한 DP]

- 무게 3의 사탕을 V3 벡터에, 무게 5의 사탕을 V5벡터에 삽입후, 내림차순으로 정렬한다

- 정렬된 V3의 구간합을 Three에 저장한다 (ex. Three[2] = V3[0] + V3[1] = Three[1] + V3[1])

- 정렬된 V5의 구간합을 Five에 저장한다 (ex. Five[3] = V5[0]+ V5[1]+ V5[2] = Five[2] + V5[2])

- 위의 2가지 과정을 하지 않으면 TLE가 발생한다(DP 사용)

- 무게 5의 사탕으로 배낭을 채울 수 있는 최대 수와 보유한 무게 5의 사탕 수 중에서 적은 값만큼의 while문을 돌린다

- 무게 5의 사탕으로 배낭을 채우고 남은 배낭의 공간 : remain

- Remain 또한 마찬가지로 Remain과 보유한 무게 3의 사탕 수 중에서 적은 값을 지닌다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<long long> v3, v5;
long long val, weight, t, s, result = 0, three[250001], five[250001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, bag;
	cin >> n >> bag;
	for (int i = 0; i < n; i++) {
		cin >> weight >> val;
		if (weight == 3) v3.push_back(val);
		else v5.push_back(val);
	}
	sort(v3.begin(), v3.end());
	reverse(v3.begin(), v3.end());
	sort(v5.begin(), v5.end());
	reverse(v5.begin(), v5.end());

	three[0] = 0;
	five[0] = 0;
	if (!v5.empty()) {
		for (int i = 1; i <= v5.size(); i++)
			five[i] = (five[i - 1] + v5[i - 1]);
	}
	if (!v3.empty()) {
		for (int i = 1; i <= v3.size(); i++)
			three[i] = (three[i - 1] + v3[i - 1]);
	}
	int lenf = v5.size(), lent = v3.size();
	int avail = bag / 5, idx = 0;
	while (idx <= min(avail,lenf)) {
		long long temp = five[idx];
		int remain = (bag - (idx * 5)) / 3;		//남은 공간에 채울 수 있는 3짜리 사탕의 최대 수
		remain = min(remain, lent);
		temp += three[remain];
		result = max(result, temp);
		idx++;
	}
	cout << result;
	system("pause");
	return 0;
}