방과후
ALGORITHM NOTE약 2분

BOJ 22988 - 재활용 캠페인

헤어에센스를 왕창 털어보자!

#algorithm#boj#gold#greedy#sorting#two-pointers
아카이브로 돌아가기

문제 링크

문제

고등학생 때였다. 친구의 손에 이끌려 처음으로 가게 된 화장품 가게는 문을 열자마자 은은한 향기가 코끝을 스치는 곳이었다. 친구를 따라가기에 급급했던 한별이의 발걸음은 이제 누가 말하지 않아도 무언가에 빨려 들어간 듯이 앞을 향했다. 파운데이션을 바르고, 블러셔를 두드리고. 거울을 본 한별이는 처음 보는 자신의 모습에 푹 빠져버렸다. 얼굴에 띈 홍조는 블러셔가 무색해질 정도였다. 그런 기분에 감화된 탓인지 화장품 가게를 나서서 집에 돌아갈 때까지도 거울의 그 모습을 잊을 수가 없었다. 마치 자기가 주목받는 느낌이 들어 볼이 한번 더 붉어져 왔다. 한별이는 이 기분을 다른 사람에게도 전해주고 싶어서 나중에 꼭 화장품 가게를 열겠다고 다짐했다.

그동안 이룬 결실도, 못다 한 각오도 있었다. 하지만 화장품 가게를 열겠다는 노력의 결과는 눈앞으로 다가와서, 내일은 한별이의 화장품 가게가 개점한 지 꼬박 1년 되는 날이 된다. 한별이의 화장품 가게는 만들어진 지 얼마 안 되었지만 많은 인기를 얻어 멀리서까지도 화장품을 사러 찾아온다. 이 화장품 가게의 인기 상품은 총 용량이 X㎖인 헤어에센스이고, 특유의 매력적인 딸기향은 모발의 상처만큼이나 마음의 상처를 치유하는 데에도 유용하다.

한별이의 화장품 가게에서는 불필요한 쓰레기를 줄이자는 재활용 캠페인을 하고 있다. 한별이의 가게의 모든 상품은 재활용이 가능한 용기에 담긴다. 가게로 사용하다 남은 헤어에센스 용기 두 개를 반납하면 새로운 용기에다가 남은 헤어에센스를 모아 주고, 추가로 총 용량의 절반만큼의 헤어에센스를 추가로 채워준다. 단, 총 용량을 넘쳐서 채워주지는 않는다. 다시 말해, 용량이 각각 A㎖와 B㎖ 남은 헤어에센스를 가져가면 min(A + B + X / 2, X)㎖의 헤어에센스가 담긴 새로운 용기로 바꿔준다.

한별이의 화장품 가게 단골인 히나는 이제까지 사모은 헤어에센스 용기가 N개 있다. i번째 용기에는 헤어에센스가 Cᵢ㎖ 담겨 있다. 히나는 한별이의 화장품 가게에 적당한 순서로 헤어에센스를 교환해서 용량이 꽉 찬, 즉 X㎖가 담겨 있는 헤어에센스 용기를 최대한 많이 만들고 싶다. 히나가 용량이 꽉 찬 헤어에센스를 최대 몇 개 만들 수 있는지 알려주자.

입력

다음과 같이 입력이 주어진다.

N X

C₁ C₂ ... Cₙ

  • N은 히나가 가진 헤어에센스 용기의 수이다. (1 <= N <= 100000)
  • X는 헤어에센스 용기의 총 용량이다. (1 <= X <= 10^18)
  • Cᵢ는 i번째 용기에 담겨 있는 헤어에센스의 용량이 Cᵢ㎖라는 의미이다. (0 <= Cᵢ <= X)
  • 입력으로 주어지는 모든 수는 정수다.

출력

한별이의 화장품 가게에 가서 적당한 순서로 헤어에센스를 교환해서 용량이 꽉 찬 헤어에센스 용기를 몇 개 만들 수 있는지 출력하여라.

풀이

핵심은 꽉 찬 용기를 만드는 경우를 세 가지로 나눠 생각하는 것이다.

  1. 이미 Ci=XC_i = X인 용기는 그대로 정답에 포함된다.
  2. 두 용기 AA, BB에 대해 A+B+X/2≥XA + B + X / 2 \ge X이면 한 번의 교환으로 꽉 찬 용기를 하나 만들 수 있다. 이는 2×(A+B)≥X2 \times (A + B) \ge X와 같으므로, 정렬 뒤 작은 값과 큰 값을 투 포인터로 묶어 최대한 많이 처리할 수 있다.
  3. 위 두 경우를 처리하고도 남은 용기들은 어느 두 개를 골라도 X / 2를 넘기지 못한다. 이때는 세 개를 모으면 최소한 하나의 꽉 찬 용기를 만들 수 있으므로, 남은 개수를 3으로 나눈 몫만큼 정답에 더할 수 있다.

코드에서는 먼저 lower_bound로 X 이상인 첫 위치를 찾아 이미 꽉 찬 용기의 개수를 바로 센다. 그보다 작은 값들만 대상으로 투 포인터를 돌리면서 2 * (C[left] + C[right]) >= X를 만족하면 한 쌍을 사용해 정답을 증가시킨다. 이렇게 짝지어 사용한 용기를 제외하고 남은 용기 수를 세어 remain / 3을 더하면 된다.

또한 X의 범위가 10^18까지 가능하므로 long long 사용이 필요하다. 비교도 X / 2를 직접 쓰기보다 (A + B) * 2 >= X 형태로 처리해 정수 연산으로 깔끔하게 비교했다.

코드

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
long long N, X;
vector<long long> C;
 
int solve() {
	int idx = lower_bound(C.begin(), C.end(), X) - C.begin();
	int left = 0;
	int right = idx - 1;
	int ans = N - idx;
	int full = 0;
 
	while (left < right) {
		if ((C[left++] + C[right]) * 2 >= X) {
			ans++;
			full += 2;
			right--;
		}
	}
	int remain = idx - full;
	ans += remain / 3;
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		long long input;
		cin >> input;
		C.push_back(input);
	}
	sort(C.begin(), C.end());
	cout << solve() << '\n';
	
	return 0;
}

복잡도

  • 시간 복잡도: O(Nlog⁡N)O(N \log N)
  • 공간 복잡도: O(N)O(N)

마무리

정렬 이후에는 이미 꽉 찬 용기, 두 개를 묶어 꽉 찰 수 있는 경우, 끝까지 남는 용기 세 그룹이라는 세 단계로 정리가 된다. 조건을 2 * (A + B) >= X로 바꿔서 보면 투 포인터 판단도 단순해져 구현이 깔끔하다.