[1052번 물병]-C++

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

2의 제곱수를 이용한 구현 문제이다. 구현이 꽤나 까다롭다고 생각했다. 난이도를 가리고 풀었는데 실버 1 밖에 되지 않아서 놀랐다.

풀이

주어진 N이 2의 제곱수인 경우부터 생각해보자.

N=4, {1,1,1,1} -> {2,2} -> {4}가 되어 총 1병으로 합쳐진다.
즉, N이 2의 제곱수인 경우에는 K(1000이하의 자연수)의 값과 상관없이 한 병도 추가로 구매하지 않아도 된다.

N의 제곱수가 아닌 경우를 생각해보자.

N=5, {1,1,1,1,1} -> {2,2,1} -> {4,1}가 되어 총 2병이 된다.
N=6, {1,1,1,1,1,1} -> {2,2,2} -> {4,2}가 되어 총 2병이 된다.
N=7, {1,1,1,1,1,1,1} -> {2,2,2,1} -> {4,2,1}가 되어 총 3병이 된다.

만약 문제에서 N=5, K=1로 주어진다면 위의 세 개의 경우, 모두 한 번에 들고 갈 수 없기 때문에 추가 구매가 필요하다.
만약 K=3으로 주어졌다면 위의 세 경우 모두 추가 구매가 필요하지 않다.

따라서, 주어진 N을 최대한 합쳐(2로 계속 나누어) 남게 마지막으로 남게 되는 병 수를 계산한 다음, 남는 병의 개수가 K보다 같거나 작으면 추가 구매가 더 이상 필요가 없게 된다.

남는 병의 개수가 K보다 크다면, N을 1씩 증가(한 병씩 추가 구매)하여 최악의 경우 N보다 큰 가장 작은 2의 제곱수가 될 때까지 병을 추가로 구매하게 된다(N=5, K=1의 경우와 같다). 중간에 남는 병의 수가 K보다 작은 경우가 생기면 추가 구매를 중단하게 된다.

코드

#include <bits/stdc++.h>

#define ll long long
#define mid (st+end)/2
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int ans;
int N,K;

void sol() {
	if(N<=K) ans = 0;

	int cnt;
	while(1) {  // N이 2의 제곱수인 경우 남는 병의 수(cnt)가 0이 되어 cnt<=K가 항상 성립
		cnt = 0;
		int tmpN = N;

		while(tmpN) {
			if(tmpN % 2) cnt++;
			tmpN /= 2;
		}

		if(cnt <= K) break;

		N++;
		ans++;
	}

	return;
}

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

	scanf("%d %d", &N, &K);
	
	sol();
	printf("%d\n",ans);
	return 0;
}

실행결과