[BOJ] 22988 재활용 캠페인

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

22988번: 재활용 캠페인

문제

 

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

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

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

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

입력

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

 N X

 C1 C2 … CN 

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

출력

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

---

풀이

못 풀고 있었는데 멘토님 캐리로 풀게 되었다 ㅋㅋ

이 문제에서의 핵심은 새로운 용기에 담기는 액체의 용량이 min(A+B+X/2,X)이므로, X㎖에 담는 용기는 재활용과정을 2번만 거치면 모두 만들어 진다는 것이다.

1. 총 용량을 벡터에 받고 오름차순으로 정렬한다.
2. 벡터의 양 끝을 포인터로 지정한다. (start,end)
3. 만약 벡터의 두 포인터가 가르키는 용량으로 꽉 찬 용기를 만들 수 있다면 ans+=1, end-=1을 해준다.
4. 꽉 찬 용기를 만들 수 없다면 remain+=1을 해준다. (여기서 remain은 꽉 찬 용기를 만들지 못하는 용기의 개수이다.)
5. start+=1을 해주면서 start>=end가 될 때까지 3,4번을 반복한다. (단, start==end라면 remain+=1을 해줘야 한다.)
6. ans+=(remain/3)을 해준다.

이 문제의 알고리즘은 위와 같은데 두 포인터를 이용하여 X㎖가 만들어지는 용기들을 모두 뺀다.

빼고 남은 용기들은 2개가 아니라 3개를 이용해야 X㎖의 용기가 되므로 나누기 3만큼의 X㎖ 용기를 만들 수 있다. (여기서 3개를 이용한다는 것은 결국 재활용과정을 2번 거친다는 것이다.)

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
ll X;
ll ans=0;
vector<ll> v;

void input() {
    cin>>N>>X;
    ll x;
    for(int i=0;i<N;i++){
        cin>>x;
        if(x>=X) ans++; // 이미 Xml보다 크다면 ans++
        else v.push_back(x);
    }
    sort(v.begin(),v.end());
}

void init() {}

void solution(){
    int start=0,end=v.size()-1; // 두 포인터를 잡는다.
    int remain=0; // 남은 용기의 개수
    
    while(1){
        if(start>=end){
            if(start==end) remain++;
            break;
        }
        if(2*v[start]+2*v[end]>=X) ans++,end--; // 두 개의 용기를 가지고 Xml를 만들 수 있는 경우
        else remain++; // 만들 수 없는 경우
        start++;
    }
    
    ans+=(remain/3); // 남은 용기는 3개를 이용해야 Xml용기 한 개를 만들 수 있다.
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}