[BOJ/Gold 4] 백준 17305 사탕 배달(C++)

문제 링크

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

17305번: 사탕 배달

 

문제

사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si를 계산해 놓았다. si는 양의 정수로, si가 클수록 사탕은 달콤하다.

shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만, 연약한 아기 석환은 가방에 최대 wg (w그램) 의 사탕만을 담을 수 있다. 아기 석환이 이 조건을 만족하면서 사탕을 담았을 때, 담아간 사탕의 당도의 합은 최대 얼마가 될 수 있을까?

입력

첫 번째 줄에 사탕의 개수 N(1 ≤ N ≤ 250,000), 무게 제한 w(0 ≤ w ≤ 5N)가 주어진다.

이후 N개의 줄에 각 사탕의 종류 ti, 당도 si가 주어진다.(ti∈{3,5}, 1 ≤ si ≤ 109)

출력

아기 석환이 조건을 만족하면서 담아갈 수 있는 사탕의 당도의 최대 합을 출력하라.

예제 입력 1

10 11
3 10
3 20
3 30
3 40
3 50
5 20
5 40
5 60
5 80
5 100

예제 출력 1

190

힌트

Java/Kotlin 사용자를 위한 경고! 일반적인 상식과 다르게, Java의 Arrays.sort 내장 함수, 그리고 Kotlin의 IntArray.sort() 는 O(N^2)시간 복잡도의 알고리즘으로 구현되어 있습니다. 이 문제의 테스트 데이터는 해당 함수를 사용하였을 때 시간 초과가 나게끔 설계되었으니, 문제를 풀 때 Collections.sort와 같은 다른 정렬 함수를 사용하십시오. 

알고리즘 분류

• 그리디 알고리즘
• 정렬
• 누적 합

풀이

최대한 당도가 높아야 하므로, 무게가 3인 사탕과 무게가 5인 사탕을 따로따로 벡터에 담은 후 내림차순으로 정렬한다.

그런 다음 무게가 3인 사탕의 당도의 누적 합을 구하고, 무게가 5인 사탕도 마찬가지로 당도의 누적 합을 구한다.

그리고 무게가 3인 사탕의 개수를 Three_Cnt라고 했을 때, 무게가 3인 사탕을 0~Three_Cnt개 가져갔다고 하자.(인덱스는 i)

그러면 무게가 5인 사탕은 (W - (i * 3)) / 5개까지 가져갈 수 있다.

이제 미리 구해둔 누적 합을 이용하여 당도의 합의 최댓값을 구한다.

그리고 무게의 합은 W가 넘으면 안 되므로, (i * 3)이 W보다 크다면 건너뛴다. 또한 (W - (i * 3)) / 5가 무게가 5인 사탕의 개수 Five_Cnt보다 크다면 무게가 5인 사탕은 Five_Cnt개만큼 가져간다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 250001
#define LL long long
#define INF 1e9

using namespace std;
LL N, W;
vector<LL> Vec[2];
LL Sum[2][MAX];
LL Answer = 0;

void Input() {
	cin >> N >> W;
	for (int i = 1; i <= N; i++) {
		LL T, S;
		cin >> T >> S;
		if (T == 3) {
			Vec[0].push_back(S);
		}
		else if (T == 5) {
			Vec[1].push_back(S);
		}
	}
}

bool Comp(LL A, LL B) {
	return (A > B);
}

void Settings() {
	for (int i = 0; i < 2; i++) {
		sort(Vec[i].begin(), Vec[i].end(), Comp);
		for (int j = 0; j < Vec[i].size(); j++) {
			Sum[i][j + 1] = Sum[i][j] + Vec[i][j];
		}
	}
	for (LL i = 0; i <= (LL)Vec[0].size(); i++) {
		if ((i * 3) <= W) {
			LL Three = Sum[0][i];
			LL R = (W - (i * 3)) / 5;
			if (R <= (LL)Vec[1].size()) {
				LL Five = Sum[1][R];
				Answer = max(Answer, Three + Five);
			}
			else {
				LL Five = Sum[1][Vec[1].size()];
				Answer = max(Answer, Three + Five);
			}
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}