1052 물병 (Java)

물병

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

풀이

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

풀이

N개의 물병이 있을 때 최종적으로 필요한 물병의 수는 N을 2진수로 표현했을 때 1의 갯수이다.
N이 1일 때 1개의 물병으로 옮길 수 있다. (이진수 : 1)
N이 2일 때 2개를 합쳐 총 1개의 물병으로 옮길 수 있다. (이진수 : 10)
N이 3일 때 2개를 합치고 나머지 1개를 따로 들고 가 총 2개의 물병으로 옮길 수 있다. (이진수 : 11)
N이 4일 때 2개씩 합치고 생긴 2개를 한번 더 합쳐 총 1개의 물병으로 옮길 수 있다. (이진수 : 100)
이러한 규칙만 찾는다면 자바에서 정수를 이진수로 바꿔주는 Integer.toBinaryString()메소드를 통해 쉽게 구할 수 있으므로 구현에는 크게 문제 될 일이 없다.
입력받은 N의 이진수를 구한 후 1의 갯수가 k보다 작을 때까지 하나씩 더해주면 되기 때문이다.

코드

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

public class Main{

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();


        System.out.println(find(n, k));
    }

    static int find(int n, int k){
        int ret = 0;

        while (true) {
            if (countOne(Integer.toBinaryString(n)) <= k) {
                break;
            }
            n++;
            ret++;
        }

        return ret;
    }

    static int countOne(String s){
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1')
                ret++;
        }
        return ret;
    }
}