Edu82(Div.2) D. Fill The Bag

 

문제를 처음 보고 정확하게 어떻게 풀어야 답이 나올지 정리를 못해서 계속 틀렸다

내가 생각한 방법은 무조건 숫자가 들어오면 계속 더해서 보관했다

그렇게하면 합치지 말아야 할 경우에 반례가 생긴다

 

방법은 작은 숫자부터 그리디하게 보면 해결된다

먼저 내가 받아온 숫자의 합이 n보다 작다면 -1이다

왜냐면 숫자를 계속 나눌수 있어서 1로 나눠서 다 합칠 경우에 어떤수든 성립 가능하다

 

만약 합이 더 클 때

Bit배열을 만들어서 계속 보관한다

 

그리고 n의 비트를 0번째부터 보면서 한번 답을 구해보자

만약 Bit[i]가 켜있다면 하나를 빼서 쓰면 된다

여기서 내가 캐치하지 못했던 부분이 있다

아래서부터 보기때문에 이제 더이상 Bit[i]는 필요없다

그래서 Bit[i+1]로 합쳐주면 된다 Bit[i+1] += Bit[i]/2 를 통해 남은걸 다 올려준다!

 

만약 Bit[i]가 없다면

이제 켜져있는 Bit를 찾아가면 된다 

j번째가 켜있다면 거리인 (j-i)만큼 답에 더해진다

그리고 j를 계속 쪼개면서 왔기 때문에 i~j까지 1씩 더해준다

i번에는 2개가 생기지만 1개를 바로 쓰기 때문에 그냥 1만 더해준다

그 후 똑같이 안쓰는 비트를 위로 올려준다!

 

그리디하게 본다면 정리가되면서 답이 나오는 문제가 많은거같다

생각할 조건이 많을때면 하나씩 조건들을 정해가면서 그리디하게 봐보자...!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int Bit[66];
 
int main(){
   int t; scanf(" %d",&t);
   while(t--){
      memset(Bit,0,sizeof(Bit));
      ll n,m; scanf(" %lld %lld",&n,&m);
      ll asum=0;
      for(int i=0;i<m;i++){
         ll x; scanf(" %lld",&x);
         asum+=x;
         ll pos=0;
         while(x!=1LL){
            pos++; x/=2LL;
         }
         Bit[pos]++;
      }
      if(asum<n) puts("-1");
      else{
         int ans=0;
         for(int i=0;i<60;i++){
            if(n&(1<<i)){
               n&=~(1<<i);
               if(Bit[i]) Bit[i]--;
               else{
                  int j=i;
                  while(!Bit[j]) j++;
                  ans+=(j-i);
                  Bit[j]--;
                  for(int k=j-1;k>=i;k--) Bit[k]++;
               }
            }
            Bit[i+1]+=Bit[i]/2;
         }
         printf("%d\n",ans);
      }
   }
}