백준 17395 이진수 변환

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

숭고한 공식 풀이는 여기서 보실 수 있습니다.

비트 연산만 안다면 쉽게 풀 수 있는 그리디 문제입니다. 1번의 변환에서 최대 1개 이상의 1이 0으로 변하므로 변환의 과정은 최대 “n을 2진수로 나타냈을 때 1의 개수”만큼 일어날 수 있습니다.

필요한 변환이 “n을 2진수로 나타냈을 때 1의 개수” 보다 크다면 조건을 만족하는 경우가 아니다. -1을 출력하고 끝내주자.

최댓값과 최솟값의 차이를 가장 작게 하기 위해서는 최댓값을 가장 작게, 최솟값을 가장 크게 해주어야 한다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> ans;
int main(void){
	ll n; int x; cin>>n>>x;
	x--;
	for(int i=60;i>=0;i--){
		if(n&(1ll<<i)){
			n^=(1ll<<i);
			ans.push_back(n);
			x--;
		}
		if(x==0) break;
	}
	if(x>0) cout<<-1;
	else{
		for(ll k:ans) cout<<k<<" ";
		cout<<0;
	}
	return 0;
}