[BOJ] 백준 [1052] 물병JAVA

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

1052번: 물병

📝문제

풀이

경우의 수 를 하나씩 따져보면 -1 을 출력할 일은 없다.

우선 물통을 안사고 최대한 합친다고 해보자
주어진 n 이 다음과 같을 때 하나씩 보자. 

case 1 : 0
case 2 : 1
case 3 : 2 1 
case 4 : 4
case 5 : 4 1 
case 6 : 4 2
...
남는 물병이 점점 늘어난다. => 병이 모자랄 일은 x
그리고 2^n 의 갯수이면 물병을 사지 않아도 된다.

ex) n=13 k=2 이면
안사고 최대한 합칠 수 있는 경우는 [8 4 1] 이다. k 보다 크다.
하지만 3병을 더 사면 [16] . 즉, 한 병에 모두 담아갈 수 있다. 

이제 k개의 물병에 나눠 가져간다고 해보자.

1. 주어진 물 n 이 k 보다 이하 라면 ? => 그냥 다 들고 가면 됨
2. 주어진 물 n 이 k 보다 작다면 ?? => 물병들을 일부 합쳐서 가져가야 됨

2번의 과정은 2^n 형태로 만드는 과정이다. 1번의 조건이 만족할 때 까지.
2^n 형태로 만들기 위해 필요한 추가 물병의 갯수를 구하면 된다.

n=13 : 물병의 갯수가 홀수이면 하나가 계속 남기때문에 1개를 추가구매한다. 그리고 2로 나눈다. => 7
n=7 : 물병의 개수가 홀수이므로 1개를 추가 구매하고 2로 나눈다. => 3
n=3 : 2 
즉 , 3개를 더 사면 n=13 k=2를 만족한다.

if( n%2 == 1) :
    n = n/2
    cnt++
    n++

이런식으로 진행하지만 비트마스킹을 이용해 풀 수 있다.

n을 2진수로 변환했을 때 1의 갯수가 k 보다 클 동안 반복 :
1이 처음으로 나타나면 합칠 때 홀수가 발생하는 숫자이므로 그 위치의 수 만큼 cnt를 늘려준다.

cnt += n&(-n)
n+=n&(-n) 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

import static java.util.Arrays.stream;


public class Main {

    static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        n = input[0];
        k = input[1];
        
        int ans = 0;

        while (Integer.bitCount(n) > k) {
            ans += n & (-n);
            n += n & (-n);
        }
        System.out.println(ans);
    }
}