[백준 코딩테스트] 백준 1052번 물병

풀이

이 문제는 비트 마스크로 접근하면 쉽게 풀린다.
자바에서는 Int 타입을 2진수로 바꾸려면 Integer.toBinaryString() 메서드를 사용하면 된다.
이때 왜 비트 마스크를 사용해야 하나면 물병 두개를 합쳐 하나의 물병으로 만들수 있는 구조는 이진수 덧셈과 같은 구조이기 때문이다. 같은 양의 물병 두 개를 하나로 합치는 과정이 이진수의 자리 올림 과정이라고 생각하면 된다.
2진수에서 1의 개수를 Integer.bitCount(n)로 한다. 여기서 나오는 1의 개수는 물병 재조합 이후에 남는 병의 개수를 의미한다.

• n = 3 -> 011 -> 병 2개
  
  위의 사진을 보면 n이 3일 때, 재조합 후 병은 1L, 2L로 총 2개이다.
  이때, 1의 개수가 k개보다 클 동안 이 과정을 반복한다. 이유는, 지민이는 k개의 갯수만큼의 물병을 한꺼번에 옮길 수 있기 때문이다. 즉, 1의 개수가 k보다 크다면 매점에서 물을 한 병씩 구매하여 옮기도록 한다.

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int answer=0;

        while (true){
            int count = Integer.bitCount(n); // 2진수로 변환한 n의 1의 갯수 카운트
            if(count <= k) break; // 이때 count는 k보다 커야하기에 
            n++;    // 1 증가
            answer++;
        }

        System.out.println(answer);
    }

}