[BOJ] 1052번: 물병 (Java)

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

1052번: 물병

 

문제

 

입력

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

 

출력

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

 

난이도

실버 1

 

Try 1

N개의 물병을 한번씩 합쳐서 N/2개로 만들려면 N이 2의 배수여야 한다고 생각하고 풀이했다. 2로 나누어떨어지지 않을 때마다 물병을 하나씩 구매한다는 의미로 1씩 더했고, 가진 물병의 개수가 1개가 될 때까지 반복문을 돌렸다. K를 고려하지 않은 잘못된 풀이이다..!

public class B1052_물병 {
    public static int N, K;
    public static int min = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 가지고 있는 물병의 개수
        K = sc.nextInt(); // 한 번에 옮길 수 있는 물병의 개수
        // = N개의 물병을 같은 용량의 물병끼리 합쳐서 K개로 만들어야 한다
        // input

        while(N>1){
            if(N%2==0){
                N /= 2;
            } else if (N % 2 == 1) {
                N++;
                min++;
            }
        }
        // operation

        System.out.println(min==0 ? -1 : min);
        // output
    }
}

 

Sol

N(int)을 이진수 형태의 배열 arr로 바꾼다. 이때 arr는 물병을 합칠 수 있는 만큼 합쳤을 때 남은 물병들이다. 예를 들어 arr가 {'1', '1', '0', '1'}이라면 8L 한 병, 4L 한 병, 1L 한 병이 남아 있는 상황이다. arr에서 1의 개수가 물병의 개수에 해당한다. 물병을 하나씩 더할 때마다 위 과정을 반복해주고, 더한 물병의 개수 min을 업데이트한다. 물병의 개수가 K보다 작거나 같아진다면 더이상 물병끼리 합치지 않아도 되는 상황이라고 판단하고 min을 출력한 후 반복문을 종료한다.

public class B1052_물병 {
    public static int N, K;
    public static int min = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 가지고 있는 물병의 개수
        K = sc.nextInt(); // 한 번에 옮길 수 있는 물병의 개수
        // = N개의 물병을 같은 용량의 물병끼리 합쳐서 K개로 만들어야 한다
        // input

        if(N<=K){
            System.out.println(0);
            return;
        } // 굳이 물병을 추가적으로 구매하지 않아도 되는 경우

        while(true){
            char[] arr = Integer.toBinaryString(N).toCharArray();
            int count = 0; // 합칠 수 있는 만큼 합쳤을 때 물병의 개수
            for(int i=0; i<arr.length; i++){
                if(arr[i]=='1') count++;
            } // 물병의 개수 count

            if(count<=K){
                System.out.println(min);
                break;
                // output
                // 물병을 계속 살 수 있기 때문에 정답이 없는 경우는 없다!
                // 즉, -1 출력 처리를 해주지 않아도 된다
            }

            N++; // 물병 한 개 구매
            min++;
        }
        // operation
    }
}

 

🙀

문제를 이해하는 데에 일단 시간이 오래 걸렸고(ㅠㅠㅋㅋ) Integer의 메서드를 찾아서 조금 헤맸다. IDE 없이도 toBinaryString()이랑 toCharArray()를 쓸 수 있게 기억해둬야겠다