Codeforces Round #529 (Div.3) C. Powers Of Two

C번) 문제 링크 : http://codeforces.com/contest/1095/problem/C

문제의 입력으로는 n과 k가 주어진다. 쉽게 설명해서 주어진 숫자 n을 k개의 2의 거듭제곱의 합으로 나누는 것이다.

사용한 방법은 우선 k와 상관없이 필요한 최소한의 개수를 구하는 것이다.

ex) n=9, k=4라고 하자. 이 때, 필요한 최소한의 개수는 1과 8 즉, 2개이다. 최소한의 개수가 구해졌다는 것은 2의 거듭제곱 형태로 나타낼 수 있다는 것이다. 이 형태는 2진수의 형태에서 1인 값들과 동일하다.

여기까지만 생각하고 바로 YES를 출력해서는 안된다. 문제에서 요구하는 YES/NO의 조건은 2의 거듭제곱의 합 형태로 나타낼 수 있느냐가 아닌 k개의 2의 거듭제곱의 합으로 나타낼 수 있느냐이다.

따라서, 구해낸 1과 8을 4개로 나눌 수 있는지를 확인해야 한다.

우선적으로 최소한의 개수를 구한 이유가 있다. 8은 2개의 4로 나눌 수 있다. 즉, 아래 자리 수가 존재한다면 1개 -> 2개로의 변형이 가능하다는 것이다. 

그렇다면 가장 높은 차수에 존재하는 숫자를 시작으로 해서 k개가 될 때까지 계속 1개씩 늘려간다면 문제를 해결할 수 있게 된다.

위와 같은 방식으로 계속해서 숫자를 줄여나간다면 전체의 합은 그대로 유지한 채 개수를 1개씩 늘려갈 수 있다.

이 과정을 k개와 같아질 때까지 진행한다면 최종적으로 필요한 숫자들을 모두 구할 수 있다.

이 때, 역시 주의해야 할 점(예외처리)이 있다. 

여기까지 잘 진행했는데 오류가 난다 ! 이는 2가지 경우를 따져주지 않았기 때문이다.

       i) 필요한 최소한의 개수가 이미 k보다 큰 경우

       ii) 전부 1로 구성될 때까지 나눴지만 k보다 작은 경우

위 2가지 경우를 추가로 생각해서 NO를 출력해주면 된다.

+ long long으로 출력하는 것도 잊지 말자 !! ( 안했다가 틀렸.. )

---

- 소스코드 -

#include<iostream>
#include<algorithm>
using namespace std;
int main(void) {
	long long n;
	int k;
	cin >> n >> k;
	int arr[31] = { 0 };
	
	long long maximum = 1;
	int upper = 0;
	int count = 0;
	int max_index = 0;
	while (n > 0) {
		maximum = 1;
		upper = 0;
		while (maximum <= n) {
			maximum *= 2;
			upper++;
		}
		upper--;
		max_index = max(max_index, upper);
		n -= maximum/2;
		arr[upper] = 1;
		count++;
	}
	if (n == 0) {
		if (count > k) {
			cout << "NO" << endl;
			
		}
		else if (count == k) {
			cout << "YES" << endl;
			for (int i = 0; i < 31; i++) {
				if (arr[i] != 0) {
					for (int j = 0; j < arr[i]; j++) {
						cout << (long long)pow(2, i) << " ";
					}
				}
			}
		}
		else {
			while (count < k&&max_index!=-1) {
				if (arr[max_index] != 0 && max_index != 0) {
					arr[max_index - 1] += 2;
					arr[max_index]--;
					if (arr[max_index] == 0) {
						max_index--;
					}
					count++;
				}
				if (max_index == 0 && count < k) {
					max_index = -1;
					break;
				}
			}
			if (max_index == -1) {
				cout << "NO" << endl;
			}
			else {
				cout << "YES" << endl;
				for (int i = 0; i < 31; i++) {
					if (arr[i] != 0) {
						for (int j = 0; j < arr[i]; j++) {
							cout << (long long)pow(2, i) << " ";
						}
					}
				}
			}
		}
	}
	else {
		cout << "NO" << endl;
	}
}