[Codeforces]1095C-Powers of Two

1095C-Powers of Two

어떤 수 n이 주어지면 그 수를 총 k개의 2의 거듭제곱수(1,2,4,8...)의 합으로 표현할 수 있는지, 가능하다면 그 조합을 출력하는 문제이다.

콘테스트 당시에는 dfs를 이용해서 풀어보려고 했으나, n=10억, k=20만이기 때문에 당연히 시간이 터진다. 그래서 왠지 dp적인 기법이 섞으면 되지 않을까 고민하다가 결국은 못 풀었다. 결론부터 얘기하면 dp가 아닌 다른 방법으로도 풀 수 있다.

만약 이 문제에서 k가 최소가 되도록 하는 문제였다면 그나마 쉽게 생각할 수 있었을 것이다. k의 최소는 엄청나게 큰 2의 거듭제곱 수부터 시작해서 대소 비교를 하면서 n에서 그 값을 뺄 수 있으면 빼고 아니면 2로 나눠가는 (마치 LCA처럼) 기법을 쓰면 k의 최소값을 구할 수 있다.  k의 최대 값은 당연히 모든 수가 2^0=1일 때이므로 n이 된다. 예를들어 n=9라면, k는 8+1 형태로 최소 2개로 표현할 수 있고, 2^0을 9개를 더하면 k=9가 된다. 그런데 k가 최소라는 보장이 없이 2보다 더 클 수 있기 때문에 최소가 되는 k값을 억지로 늘려야 하는 상황이 된다. 또한 나는 여기서 k의 최소값과 최대값 사이의 모든 범위에서 k가 가능한지도 확신이 없었는데(중간에 안되는 값이 생길지도 모른다는 의심), 결론은 모든 범위에서 반드시 가능하다. 이는 밑에서 설명하겠다.

이처럼 k가 최소인 3일때부터 n과 값이 같아지는 7까지 2의 거듭제곱 꼴의 수를 쪼개면 1개가 늘어나므로, 원하는 k값을 자유자재로 맞출 수가 있다. 

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> ans;
priority_queue<int> pq;
int n,k;
int check[200009];
int possible=-1;
 
int main(){
    scanf("%d %d",&n,&k);
 
    int big=1,cnt=0;
    for( ; big<=1e+9 ; big*=2);
 
    int cur=big;
    int tmp=n;
    while(tmp>0){    
        while(cur>tmp){
            cur/=2;
        }
        tmp-=cur;
        pq.push(cur);
        cnt++;
    }
 
    if(cnt<=k && n>=k){
        printf("YES\n");
        
        while(pq.size()!=k){
            int top=pq.top();    pq.pop();
            pq.push(top/2);
            pq.push(top/2);
        }
 
        while(!pq.empty()){
            printf("%d ",pq.top());
            pq.pop();
        }
    }
 
    else printf("NO\n");
    return 0;
 
}

구현은 우선 최소 k값을 구하면서 2의 거듭제곱 꼴을 우선순위 큐(pq)에 넣는다. 그런 다음, k값과 같아질 때까지 pq의 top에서 값 하나를 꺼내서 둘로 쪼갠 다음에 다시 넣는 행위를 반복하면 된다. 사실 굳이 pq를 쓸 필요없이 일반 queue를 써도 되기는 하지만, 1은 쪼갤 수가 없기 때문에 따로 예외 처리를 하기 보다는 그냥 pq를 사용했다. Max heap은 1까지 top에 올 일이 없다.