[백준, Java] 1052번 : 물병

🔗 문제 링크

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

😮 문제 해결 방법

문제에서 같은 양이 들어있는 물병끼리 하나로 합칠 수 있고 처음에는 모든 물병에는 물이 1L가 들어있다고 제시되어 있다.

처음부터 두 개의 물병을 한 개의 병으로 합쳐가면, 2L → 4L → 8L 이런식으로 증가할 수 밖에 없다.

이는 물병이 2의 제곱 값이 되어야 병이 하나로 합쳐지는 것을 알 수 있다.

 

N개의 물병을 K개의 물병으로 합치는 경우 최소 개수의 물병을 사기 위해선 남은 물병(N) 보다 작으면서 가장 큰 2의 제곱 값을 매번 구해 빼주는 작업을 K-1번 해주고,

그래도 물병이 남아있다면 마지막(K번째)에는 남은 물병으로 한 병을 만들어야 하므로 남은 물병보다 크면서 가장 작은 2의 제곱값을 구해 빼주면 사야하는 물병이다.

 

예를 들어 N이 43 K가 3이라면 , 32개로 1병을 만들고, 남은 11개의 물병에서 8개로 또 1병을 만든다. (K-1번 진행 = 2번)

그리고 남은 3병을 한 개의 병으로 합치기 위해선 4병으로 만들어 주면 1병으로 만들 수 있다. 따라서 4-3인 1병을 추가로 구매해주면 된다. (남은 1번 진행)

 

만약 K-1번 만드는 도중 남은 물병의 개수가 없는 경우 K개 내에서 모든 물병을 합칠 수 있는 경우이므로 추가로 구매하지 않아도 되기 때문에 0을 리턴한다.

 

1. K-1번 반복하면서 남은 물병보다 작고 그 중 가장 큰 2의 제곱 값을 구해 최대한 많은 물병을 이용해 하나의 물병으로 만든다.
   • 만약 K-1번 반복하면서 남은 물병이 0개라면 모든 물병이 K개 이내로 만들어지는 경우이므로 추가구매를 할 필요가 없다. 0을 리턴한다.
2. 물병이 남아있는 경우 K-1개 물병을 만들었으므로, 마지막 물병은 남은 물병보다 크면서 가장 작은 2의 제곱값을 구한 뒤 남은 물병을 빼주면 구매해야 하는 물병 개수이다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_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 rst = buyBottle(N, K);
        System.out.println(rst);
        br.close();
    }

    private static int buyBottle(int n, int k) {
        /**
         * 1. K-1번 돌면서 남은 물병 보다 작은 2의 base 제곱 값 빼주기 (최대한 많은 물병을 이용해 하나로 만들기)
         * 2. 마지막은 해당 수보다 큰 2의 base 제곱 값 구해서 남은 물병 빼주기
         */
        if(n <= k) return 0;

        // 1. K-1번 돌면서 남은 물병 보다 작은 2의 base 제곱 값 빼주기 (최대한 많은 물병을 이용해 하나로 만들기)
        for (int loop = 0; loop < k - 1; loop++) {
            int base = 0;
            while (Math.pow(2, base) < n) {
                base++;
            }
            n -= Math.pow(2, base - 1);

            // 남은 물병이 없는 경우 더이상 물병을 살 필요가 없으므로 return 0
            if(n == 0) return 0;
        }

        // 2. 마지막은 해당 수보다 큰 2의 base 제곱 값 구해서 남은 물병 빼주기
        int base = 0;
        while (Math.pow(2, base) < n) {
            base++;
        }
        return (int) Math.pow(2, base) - n;
    }
}