[BOJ 1052] 물병
- 문제풀이
본문
지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.
물은 다음과 같이 재분배 한다.
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.
이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.
예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.
입력
첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 512MB |
풀이
모든 물병에는 물이 $1$리터 들어있고, 같은 양의 물이 들어있는 물병 2개를 합쳐 물병 1개를 만들어낸다. 즉, 모든 물병에 들어있는 물의 양은 모두 $2^x$리터 꼴로 존재한다. 그리고 어떤 수 $N$이 주어졌을 때, 물병의 수를 최소화하기 위해 물병들을 최대한 합친다면 그 결과는 항상 하나로 결정된다. 바로 숫자 $N$을 이진수화한 결과와 같아진다!
즉, 어떤 수 $N$이 주어졌을 때, 물병들을 합쳐 만들 수 있는 최소의 물병 갯수는 숫자 $N$을 이진수로 나타냈을 때 존재하는 1의 개수와 같다. 그리고 우리는 이 1의 개수가 $K$개 이하가 되도록 조절하는 것이 목표이다. 만약 답이 없다면 -1을 출력하라는 지시도 있다. 생각해보면 알겠지만, 우선 답이 존재하지 않는 경우는 없다. 모든 숫자 $N$은 어떤 수 $x$에 대해 $N \leq 2^x$일 것이므로, 항상 물병들을 추가하여 물병의 수를 1개로 만들 수 있기 때문이다. 문제에서 주어지는 제한에서 $K$는 자연수이므로 -1을 출력하는 경우는 생각할 필요가 없다.
그럼 답은 어떻게 계산할 수 있을까? 우선 숫자 $N$이 주어질 때, 물병들을 최대한 합쳐서 현재 물병의 개수 $N_{bottle}$을 계산하자. 이것은 $N$을 이진수로 나타낸 다음 1의 개수를 세면 된다. 그 다음 $N_{bottle}$과 $K$를 비교해보며 답을 추론해보자.
- $N_{bottle} \leq K$라면, 물병을 더 추가하지 않아도 이미 물병을 $K$개 이하로 만들었다. $ans = 0$
- $N_{bottle} > K$라면, 물병을 더 추가하여 물병의 개수를 줄여야한다
- 최소한의 물병을 추가해야하므로, 가장 작은 비트부터 제거해나가면서 물병의 개수를 줄여나가면 된다
- 주어지는 숫자 $N \leq 10^7$이므로, $N$을 이진수로 나타내었을 때 그 길이는 최대 24글자이다 ($2^{23} < 10^7 < 2^{24}$)
코드를 구현하기 위해 먼저 1가지 함수를 구현하자. get_bottle_count(x) 함수는 $x_{bottle}$를 계산하는 함수다. 비트 길이가 최대 24글자였으므로, 이 함수를 한참 실행해도 시간복잡도에는 큰 영향을 주지 않을 것 같다. 물병을 추가할 때마다 $N$이 변화할 것이므로, 그 때마다 $N_{bottle}$을 계산하도록 하자. 계산 결과가 $K$ 이하가 되는 순간 물병을 더 추가할 필요가 없고, 그 때까지 추가한 물병의 개수를 출력하면 된다.
물병을 추가하는 방법은 아까도 얘기했듯이, 가장 작은 비트를 제거하는 수부터 진행하면 된다. 즉, $i=1$부터 시작하여 계속해서 2배씩 증가시켜가며 비트를 제거할 수 있는지 탐색한다. 꼭, 비트를 제거할 수 있을 때에만 $i$개의 물병을 추가해야한다. 비트를 제거할 수 없는 상황에서 $i$개의 물병을 추가하면 오히려 $N_{bottle}$을 늘리게 된다! $N$의 최댓값이 $2^{24}$보다 작으므로, 이 과정도 24번 이내에는 완료될 것임을 예상할 수 있다. 이 과정을 반복하면 쉽게 구현할 수 있다.
소스코드
Github Link : Source Code
참고 알고리즘 : 그리디 알고리즘