백준 1052번 - 물병

1052번: 물병 (acmicpc.net)

1052번: 물병

1리터의 물이 들어있는 n개의 물병을 이용해 k개를 넘지 않는 비어있지 않은 물병을 만드는 문제이다. k개 이하의 물병을 만들기 위해서 상점에서 추가적으로 1리터의 물이 들어있는 n개의 물병을 사올 수 있는데, 이때 최소한으로 사오는 갯수를 구하여야 한다.

물은 아래와 같이 재분배한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

.

#include <iostream>

using namespace std;

int test(int a) {
	int b = 0;
	while (1) {
		if (a == 1) {
			b++;
			break;
		}
		if (a % 2 == 1) {
			a--;
			b++;
		}
		else {
			a = a / 2;
		}
	}
	return b;
}

int main() {
	int n, k,a=0,b=1;
	cin >> n >> k;
	if (k >= n) {
		cout << 0;
	}
	else {
		while (1) {
			if (test(n)<=k) {
				break;
			}
			if (n % 2 == 0) {
				n = n / 2;
				b = b * 2;
			}
			else {
				n = n + 1;
				a = a + b;
			}
			
		}
		cout << a;
	}
}

 

나의 접근 방식은, 우선 같은 양의 물을 합칠 수 있을 만큼 합친 후, 홀수개가 되어 물병이 남게 될 경우 상점에서 추가로 물병을 사와 짝수개로 만들어주어 다시 합치는 방식으로 구현하였다. 예를 들어 100개의 물병이 있을 때 25개까지 합칠 수 있는데, 이 25개의 물병 각각의 물 양은 4리터가 될 것이다. 따라서 물병을 26개로 만들기 위해 상점에서 1리터 *4개의 물병을 사왔다.  이 과정에서 2,4,8,16,... 등 2의 제곱수만큼의 물병이 사올 때 마다 더해지게 된다.

루프 중 합쳐진 물병의 개수가 주어진 k개 이하로 나누어질 수 있는 경우 (이는 test함수를 구현하여 확인함. test의 경우 n을 2로 나눌 수 있을 만큼 나누고, 홀수가 된 경우 물병 하나를 빼는것과 동일하게 n에 -1을 해주었다. 최종적으로 n을 1까지 나누면 빼둔 물병에 n+1을 해주면 n개 물병을 합친 최솟값을 구할 수 있다.) 루프를 탈출하고 최종적으로 값을 출력하면 된다.