티스토리 뷰

 

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

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

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

 

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

먼저 내가 받아온 숫자의 합이 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만 더해준다

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

 

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

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

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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);
      }
   }
}
 
 

'알고리즘 > Codeforces' 카테고리의 다른 글

R621(Div.1+Div.2) A. Cow and Haybales  (0) 2020.02.19
R620(Div.2) D. Shortest and Longest LIS  (0) 2020.02.18
R620(Div.2) C.Air Conditioner  (0) 2020.02.16
R620(Div.2) B.Longest Palindrome  (0) 2020.02.16
R619(Div.2) B. Motarack's Birthday  (0) 2020.02.16
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함