1052번: 물병
지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번
www.acmicpc.net
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개 물병을 합친 최솟값을 구할 수 있다.) 루프를 탈출하고 최종적으로 값을 출력하면 된다.
'백준' 카테고리의 다른 글
| 백준 1074번 - Z (0) | 2023.07.25 |
|---|---|
| 백준 1291번 - 이면수와 임현수 (0) | 2023.07.24 |
| 백준 1002번 - 터렛 (0) | 2023.07.23 |
| 백준 1051번 - 숫자 정사각형 (0) | 2023.07.21 |
| 백준 2108번 - 통계학 (0) | 2023.07.21 |
