백준 - 1052번. 물병

이 문제의 링크

https://www.acmicpc.net/problem/1052

1052번: 물병

 

 

이 문제는 잔디를 깔기위해 후다닥 문제를 풀었으나 실제로는 이를 이해하는데 오래 걸려서 이를 포스팅하게 되었다. 내가 문제를 풀면서 막혔던 부분은 해당 문제의 예제 3인 1000000 5 이다. 숫자가 커지니 문제 그대로를 Array나 List와 같은 자료구조에 담아서 일일히 비교하는 것은 불가능했다. 따라서 이를 해결하고자 % 방법을 생각한 것은 좋았지만, 이를 어떻게 응용해야하는지 생각이 나지 않았다.

 

 

따라서 이를 구글링해봤고 그 결과, 이 문제의 해결방법은 이진수로 바꾸면 된다는 해결책을 찾게 되었다. 왜냐면 이진수는 같은 크기가 두개 있으면 0으로 되기 때문에 이진수로 변경했을 때의 1의 개수가 결국 물병의 개수라는 것을 알 수 있다!! 예를 들어 N = 13, K = 2일 때 13을 2진수로 변환하면 1101이 된다. 이는 물병의 개수가 3개라는 의미이므로 새로운 물병을 추가해야한다. 1을 추가한 14를 이진수로 변경해보면 1110 이므로 이 또한 불가능하다. 다시 1을 추가한 15의 경우에는 1111으로 물병의 수가 4개가 된다. 마지막으로 1을 한번 더 더한 16은 10000이 되므로 물병의 수가 1이 되어 성립이 됨을 알 수 있다.

 

그래서 이를 이용한 문제풀이 방법을 하단에 첨부한다.

 

 

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

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 new_bottles_cnt = 0;
        while(true){
            int cnt = (int) Integer.toBinaryString(N).chars().filter(i -> i == '1').count();
           if(cnt <= K)
               break;
           new_bottles_cnt++;
           N++;
        }
        System.out.println(new_bottles_cnt);
    }
}