[BOJ 1052] 물병 (Java) - 이진수 1의 개수와 비트 트릭 n & (-n) 풀이

문제 정보

• 문제 링크: 백준 1052번 - 물병
• 난이도: Silver I
• 시간 / 메모리 제한: 1초 / 512 MB

핵심 조건 요약

• 처음에 물이 1L씩 들어 있는 물병 N개를 가지고 있습니다.
• 같은 양의 물이 들어 있는 물병 두 개를 골라 한쪽에 물을 모두 붓는 작업을 반복해, 비어 있지 않은 물병이 K개 이하가 되도록 만들어야 합니다.
• 부족하면 상점에서 1L짜리 물병을 새로 살 수 있을 때, 구매해야 하는 물병의 최솟값을 구합니다. (불가능한 경우 -1)

변수	범위	비고
물병 수 N	1 ≤ N ≤ 10^7	int 범위 내 표현 가능
목표 개수 K	1 ≤ K ≤ 1,000	K ≥ 1이므로 사실상 항상 달성 가능 (-1 불가)

---

접근 아이디어

1. 물병 합치기 = 이진수 표현의 1의 개수

1L짜리 물병들을 같은 양끼리 합치면 만들 수 있는 물병의 용량은 항상 2^0(1L), 2^1(2L), 2^2(4L), 2^3(8L), ... 형태가 됩니다. 따라서 추가 구매 없이 N개의 물병을 최대한 합쳤을 때 남는 물병의 최소 개수는 **N을 이진수로 나타냈을 때 1의 개수(Integer.bitCount(N))**와 정확히 같습니다!

예를 들어 N = 13, K = 2를 살펴봅시다.

• 13을 이진수로 쓰면 1101(2) = 8 + 4 + 1 → 최소 물병 3개(8L, 4L, 1L)가 남습니다. (3 > K)
• 이때 상점에서 물병을 더 사면 결국 13 + ans의 이진수에서 1의 개수가 K 이하가 되는 최소 ans를 찾는 문제로 바뀝니다.
• 13에 3을 더하면 16 = 10000(2)이 되어 물병 1개(16L)에 모두 담을 수 있으므로 정답은 3입니다.

참고: K >= 1인 자연수이므로 물병을 계속 사서 N을 가장 가까운 2^m으로 올리면 언제나 물병 1개(1 <= K)로 합칠 수 있습니다. 따라서 -1을 출력하는 경우는 존재하지 않습니다.

2. 최하위 1비트(LSB)를 한 번에 지우는 n & (-n) 트릭

1씩 더해가며 bitCount(n)을 확인해도 되지만, **가장 작은 용량의 물병(1이 켜진 최하위 비트)**을 한 번에 합치면 훨씬 빠르게 점프할 수 있습니다.

• 2의 보수 표현에서 -n = ~n + 1이므로, **n & (-n)은 n의 이진수에서 가장 오른쪽에 있는 1비트 값(예: 13 = 1101(2)이면 1, 12 = 1100(2)이면 4)**을 즉시 반환합니다.
• 현재 가장 작은 물병의 크기가 lsb = n & (-n)이라면, 이 물병과 짝을 맞춰 다음 단계(2 * lsb)로 합치기 위해 필요한 최소 1L 물병 개수가 정확히 lsb개입니다!
• 따라서 Integer.bitCount(n) > k인 동안 다음을 반복하면 됩니다.
  1. ans += n & (-n)
  2. n += n & (-n)

단계 (N=13, K=2)	n (이진수)	bitCount(n)	lsb = n & (-n)	누적 구매 ans
초기	13 (1101)	3 (> 2)	1	0
1회차	14 (1110)	3 (> 2)	2	1
2회차	16 (10000)	1 (≤ 2)	종료	3

---

Java 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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;

        // 현재 물병 개수(켜진 비트 수)가 K 이하가 될 때까지 최하위 비트만큼 구매해 합침
        while (Integer.bitCount(n) > k) {
            int lsb = n & (-n);
            ans += lsb;
            n += lsb;
        }

        System.out.println(ans);
    }
}

---

채점 결과

---

복잡도 분석

• 시간 복잡도: O(log N) — 매 반복마다 최소 하나의 1비트가 자리올림으로 사라지므로 최대 비트 수(약 24회) 이내에 종료됩니다.
• 공간 복잡도: O(1) — 추가 배열 없이 상수 공간만 사용