[백준] 1052. 물병

문제 링크

[백준] 1052. 물병

풀이 과정

위의 예시처럼, 물을 재분배하는 과정은 10진수를 2진수로 변환하는 작업이라고 볼 수 있습니다.

위 사진은 3개의 초기 물병에 한 개의 물병만을 추가해 1개의 물병을 만드는 과정을 보여줍니다. 한 개의 물병을 추가한다는 것 자체가, 초기 시작을 4개의 물병으로 하는 것과 동일한 결과를 보여주는 것을 알 수 있습니다. 또한, K개의 물병을 만든다는 것은 곧 물병의 총 개수를 이진수로 변환했을 때의 1의 개수와 동일하다는 것도 알 수 있습니다.

따라서, N보다 큰 수 중, 이진수로 변환했을 때의 1의 개수가 K 이하인 수를 찾아 출력하면 됩니다.

또한, N은 최대 $10^7 = 10,000,000$ 이고, 이는 이진수로 표현할 시 비트 30개( $2^{30} \approx 10^9$ )면 충분하므로, -1이 정답이 될 수는 없어서 코드로 작성하지 않았습니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int answer = 0;

        while (true) {
            char[] binary = Integer.toBinaryString(N).toCharArray();
            int cnt = 0;

            for (int i = 0; i < binary.length; i++) if (binary[i] == '1') cnt++;

            if (cnt <= K) {
                System.out.println(answer);
                break;
            }

            N++;
            answer++;
        }
    }
}