[백준 01052] 물병 [Java]

문제

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

 

---

풀이

N개의 병을 2개씩 합쳐서 하나의 병으로 만드는 문제다.

만약 K개의 병으로 만들 수 없다면 병을 한 개 더 추가해 다시 합칠 수 있다.

2개의 병을 한 개의 병으로 합치기 때문에 N을 최대로 합칠 수 있는 병의 수는 N을 이진수로 했을 때 1의 개수와 동일하다.

예제 1번은 다음과 같다.

1 1 1 1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 1

4 4 4 1

8 4 1

$13=1101_{(2)}$으로 필요한 병의 수는 3개지만, K는 2이므로 병을 더 추가해야 한다.

$14 = 1110_{(2)}$에 대해 K는 2, 추가된 병은 1개다. 14개의 병을 합쳐 총 3개의 병에 { 8, 4, 2 }담을 수 있다.

이를 코드로 구현하면 다음과 같다.

병의 수를 한개씩 늘려주면서 N이 가지는 1의 수가 K이하가 될 때 까지 병을 추가하면 된다.

        int cnt = 0;
        while (Integer.bitCount(N) > K) {
            ++N;
            ++cnt;
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01052.java