[BOJ] 1052번 물병

개요

N개의 물병의 물을 옮겨 담아 K개 이하로 만들어야 하는 문제

비트마스킹을 이용하면 짧은 코드로 해결 가능하다.

문제링크

코드

import java.io.*;
import java.util.StringTokenizer;

public class Baekjoon1052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int newBottles = 0;

        while(Integer.bitCount(n++) > k) {
          newBottles++;
        }
        
        bw.write(newBottles+"\n");
        bw.flush();
    }
}

해결 과정

N개의 물병을 K개의 물병으로 만들기 위해서는 다음과 같은 작업을 반복한다.

같은 양의 물이 들어있는 물병 두 개 중 하나를 다른 하나의 물병에 부어 하나로 만든다.

만약 위 과정을 통해 K개의 물병을 만들 수 없으면 새 물병을 사서 해결시켜 줄 수 있는데 이 때 새로 사야하는 물병의 갯수를 반환하는 문제이다.

그렇다면 어떤 상황일 때 새로운 물병이 필요할까?

K가 1일 경우를 살펴보자

in     out
2 1  -> 0
3 1  -> 1
4 1  -> 0
5 1  -> 3
6 1  -> 2
7 1  -> 1
8 1  -> 0
9 1  -> 7
10 1 -> 6

여기서 우리가 알 수 있는 사실은 2의 n제곱마다 물병하나로 합칠 수 있다는 사실이다.

이것은 조금만 생각해보면 알 수 있는데 같은 양이 든 물병 두 개를 합치는 거면 2의 제곱으로 커지기 때문이다. (ex: 1 + 1 = 2, 2 + 2 = 4, 4 + 4 = 8…)

그리고 좀 더 나아가 생각해보면 십진수를 이진수로 표현해 n개의 물병이 몇 개의 물병으로 합쳐지는지 알 수 있다.

8을 이진수로 표현하면 1000가 되고 합쳐진 물병은 1개가 된다. (8리터 물병 1개) 13을 이진수로 표현하면 1101가 되고 합쳐진 물병은 3개가 된다. (8리터, 4리터, 1리터 물병 한개씩으로 총 3개의 물병으로 합쳐진다)

여기까지 왔으면 k개의 물병을 만들기 위해 몇 개의 추가 물병이 필요한지 계산할 수 있다.

예를 들어 15개의 물병을 3개의 이하의 물병으로 만들어야 한다고 하자

15를 이진수로 변환하면 1111이 되고 모두 합친 후에 물병은 4개(8,4,2,1) 필요하다.

여기서 추가로 물병을 하나 더 주면 16이 되고 이진수로 10000이 되어 필요한 물병이 1개로 줄어든다.

이렇게 n개의 물병에서 시작해서 k개 이하의 물병을 만들 수 있을 때까지 물병을 하나씩 추가해가면서 확인하면 해답을 구할 수 있다.

이것을 코드로 표현한 것이 다음 코드이다.

int newBottles = 0;

while(Integer.bitCount(n++) > k) {
    newBottles++;
}

결과