백준 1052번 - 물병

문제

백준 1052번 - 물병

---

아이디어

• 예제 입력 2 N=13, k=2로 일단 문제 그대로 따라해봤다.

초기 상태

1번 재분배 후

2번 재분배 후

3번 재분배 후

• 이제 재분배 할 수 없다.
• 남은 숫자들이 뭔가 익숙하다. 1101, 즉 13을 이진수로 표현한 값이다.
• 여기서 물병을 하나 추가하면 다음과 같다.

물병 1개째 추가 & 재분배

• 1110, 14가 되었다.

물병 2개째 추가 & 재분배 안됨

• 1111, 15가 되었다.

물병 3개째 추가 & 재분배

• 10000, 16이 되었다.
• N을 이진수로 변환했을 때 1의 개수가 비어있지 않은 물병의 개수다.
• N을 1씩 증가시켜 이진수로 변환했을 때 1의 개수와 k를 비교해 k가 작아질 때까지 반복한다.
• 자바에는 bitCount()라는 간편한 메서드가 존재한다.

예상 시간 복잡도

• 예상 시간 복잡도 : 약 O(log N)

코드 구현

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

public class BJ_1052 {
    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 count = 0;
        while (Integer.bitCount(n) > k) {
            n++;
            count++;
        }
        System.out.println(count);
    }
}