백준 - 22988 재활용 캠페인 [투포인터]

 

22988번: 재활용 캠페인

 

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;
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/22988.%E2%80%85%EC%9E%AC%ED%99%9C%EC%9A%A9%E2%80%85%EC%BA%A0%ED%8E%98%EC%9D%B8