백준 1052번 물병 C++

출처 : https://www.acmicpc.net/problem/1052

 

우선 n<=k이면 물병을 구매하지 않아도 바로 옮길 수 있으므로 0을 출력하고 프로그램을 종료하였다.

그리고 그리디적으로 k>1일 동안 n에서 n을 넘지 않는 최대의 2의 제곱을 빼가면서 n을 줄였다. 물론 k도 1씩 줄여줬다.

빼는 도중에 혹은 while문을 빠져나왔을 때 n이 0이라면 물병을 더 구매할 필요가 없기 때문에 0을 출력하고 프로그램을 종료하였다.

n가 0이 아닌 경우에는 n보다 큰 2의 제곱 중 가작 작은 수에서 n을 빼면 구매해야하는 물병의 최솟값이다.

 

출력 조건에 정답이 없을 경우에는 -1을 출력하라고 했는데, 정답이 없을 경우는 없을 것 같아서 만들지 않았는데 통과되었다. 속임수였던 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	int cnt = 0;
	if (n <= k) {
		cout << 0;
		return 0;
	}
	int start = 1;
	while (start < n) {
		start *= 2;
		cnt++;
	}
	while (k > 1) {
		if (n == 0) break;
		while (true) {
			if (pow(2, cnt) <= n) {
				n -= pow(2, cnt);
				break;
			}
			cnt--;
		}
		k--;
	}
	if (n == 0) {
		cout << 0;
		return 0;
	}
	start = 1;
	while (start < n) {
		start *= 2;
	}
	cout << start - n;
};