BOJ 22988(재활용 캠페인)풀이

이미지를 누르면 문제로 이동합니다

 

(한별이가 나오는 몇 안 되는 희귀한 문제이다.)

이 문제는 한가지 관찰만 하면 쉽게 풀 수 있다. 그 관찰은 바로 많아도 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있다는 것이다. 만약 a 용기에 0ml가 있고 b 용기에 1ml가 있고 총용량이 10ml 일 때 a와 b를 합치면 1+5=6ml가 된다. 그리고 c 용기에 2ml가 있다고 하고 앞에서 구한 6ml 용기와 c를 더하면 6+2+5로 10ml를 넘어간다. 이걸 하나의 식으로 나열하면 a+b+c+10/2+10/2 가 된다. 즉 a, b, c 모두 0ml 이어도 10/2 가 두 번 더해져 10으로 꽉 찬 용기가 되기 때문에 최대 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있는 것이다. 

 

맨 처음에 정렬을 해준 뒤 C[i]가 X와 같다면 혼자서도 꽉 찬 용기가 되기 때문에 개수에 +1 해준다. 그리고 혼자 꽉 찬 용기가 되지 않을 경우 작은 값을 a, 큰 값을 b라고 했을 때 (a + b) + X / 2 >=x => (a + b) >= x / 2  => 2 * (a + b) >= x 가 된다. 그러므로 양 쪽 끝에서 탐색을 하면서 오른쪽 값(큰값) 왼쪽 값(작은 값)의 합 * 2가 X가 넘는지 확인해주면 된다. 오른쪽 값 즉 큰 값이 줄어들게 되면 그에 따라 작은 값은 커져야 되기 때문에 작은 값은 위 조건에 맞게 계속 증가시켜주면 된다. 그렇게 혼자서 꽉 찬 용기가 되는 용기들과 두 개를 합쳐서 꽉 찬 용기들의 개수를 전체 개수에서 뺀 나머지 개수에 3으로 나눈 몫을 구해준 뒤 더해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[200000];
int main()
{
    ll a,b,c,ans=0;
    scanf("%lld %lld",&a,&b);
    for(int i=0;i<a;i++){
        scanf("%lld",&l[i]);
    }
    sort(l,l+a);
    ll left=0,right=a-1;
    ll ct=0;
    while(left<right){
        if(l[right]==b||l[left]==b){
            if(l[right]==b){right--;ct++;ans++;}
            if(l[left]==b&&right+1!=left){left++;ct++;ans++;}
        }else{
            while(left<right&&(l[left]+l[right])*2<b)left++;
            if((l[left]+l[right])*2>=b&&left!=right){ans++;ct+=2;}
            right--;
            left++;
        }
    }
    //printf("%lld\n",ans);
    if(a==1){
        if(l[0]>=b)printf("1\n");
        else printf("0\n");
    }else printf("%lld\n",ans+(a-ct)/3);
    
}