백준 - 22988 재활용 캠페인 [투포인터]
22988번: 재활용 캠페인
첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용
www.acmicpc.net
1. 문제 요약
헤어에센스 용기의 수 n, 용기의 용량 x, 각 용기에 현재 들어있는 양의 수열 arr이 주어진다.
용기 2개를 갖다 주면, 두 용기에 남아있는 잔량 + x/2 만큼 채워진 헤어에센스를 준다.
단, 용기의 용량보다 넘치게 주지는 않는다.
현재 가지고 있는 용기를 이용하여 가득 찬 헤어에센스를 최대 몇 병 만들 수 있는지 구하시오.
2. 접근 방법
- 이미 가득 찬 용기를 걸러내어 그 개수를 정답에 더해준다.
- 용기들을 오름차순으로 정렬한다.
- 투포인터 알고리즘을 사용하여 두 개의 용기를 더하여 가득 찬 용기를 만들 수 있는 경우 정답에 더해주고, 현재 용기의 잔량 개수에서 차감해 준다.
- 정답 + 남은 용기의 개수를 3으로 나눈 몫을 출력한다.
2 - 1. 남은 용기의 개수 // 3을 하는 이유?
가득 찬 용기를 만들기 위해서는 두 용기를 더해서 x/2를 만들면 가득 찬 용기를 얻을 수 있습니다.
즉, a1 + a2 >= x/2 이 만족할 경우, 가득 찬 용기를 얻을 수 있습니다.
n = 3, x = 10, arr = [0, 0, 0] 일 때,
0짜리 두 개를 가져가면 0 + 0 + x/2 만큼 채워진 새로운 병을 줍니다.
그러면 이 새로운 병과 남아있던 0짜리 병 두 개를 가져가면 5 + 0 + x/2의 새로운 병을 줍니다.
위 a1 + a2 >= x2를 만족하므로 가득 찬 병을 얻을 수 있습니다.
즉, 남은 용기의 용량과 관계없이 3개의 용기를 가져가면 최소 1개의 새로운 용기를 얻을 수 있습니다.
문제에서는 최대 얻을 수 있는 개수를 구하라 했으므로,
이미 가득 찬 용기를 구하여 정답에 더하고,
a1 + a2 >= x/2를 만족하는 용기를 구하여 정답에 더하고,
남은 용기 // 3을 더해주면 최대 개수를 구할 수 있습니다.
3. 파이썬
n, x = map(int, input().split())
arr = sorted([a for a in map(int, input().split()) if a < x])
answer = n - len(arr)
n -= answer
target = x /2
i = 0
j = n - 1
while i < j:
if arr[i] + arr[j] >= target:
answer += 1
i += 1
j -= 1
n -= 2
else:
i += 1
print(answer + n//3)
4. 자바
private static int solution(int n, long x, long[] arr) {
arr = filterAndSort(arr, x); // 가득찬 용기를 걸러내고, 오름차순으로 정렬
int answer = n - arr.length;
n = arr.length;
int i = 0;
int j = n - 1;
while (i < j) {
if ((arr[i] + arr[j]) * 2 >= x) {
answer++;
i++;
j--;
n -= 2;
} else {
i++;
}
}
return answer + n / 3;
}