[백준 1052번][Java] 물병 - 다른 풀이

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

1052번: 물병

 

풀이 방법

 

이 풀이 방법은 아주 직관적이고 쉽습니다.

 

1. 1L 물병의 개수가 2의 제곱수인 경우, 하나의 물병에 옮길 수 있다는 점을 이용해, N을 2의 제곱수로 분해한다.

(이때 분해된 개수가 물병의 개수다.)

2.  물병의 개수가 K보다 크다면 크기가 작은 물병들부터 합쳐나간다.

 

예를 들어, N = 11인 경우 8, 2, 1로 분해할 수 있겠죠. 이는 세 개의 물병에 각각 8L, 2L, 1L가 들어있는 것과 같습니다.

만약 K값이 3이상이라면 물병을 추가할 필요없이 0을 리턴하고 종료하면 됩니다.

 

하지만 K가 1이나 2라면 물병을 합쳐야겠죠?

이 방법도 매우 간단합니다.

K = 2이라고 가정해보죠.

물병들을 저장한 리스트나 덱에서 가장 작은 두 개의 물병(1L, 2L)을 빼주고, 합쳐진 물병(4L)을 다시 추가해줍니다.

1L, 2L를 합치기 위해서 필요한 물병의 수는 2-1 = 1개 입니다.  물병은 2개가 되고 [8, 4]가 됩니다.

물병의 수가 K를 만족하게 됐네요. 필요했던 물병의 수는 1개이므로 1개를 리턴해주면 끝.

 

 

 

 

...
public class Main {
    static int N, K;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        ArrayDeque<Bottle> bottles = grouping(N);
        if(bottles.size() <= K) {
            System.out.println(0); return;
        }

        int ret = pouring(bottles);
        System.out.println(ret);
    }

    private static ArrayDeque<Bottle> grouping(int n) {
        ArrayDeque<Bottle> bottles = new ArrayDeque<>();
        while(n > 0) {
            int amount = getTwoSquareLowerOrEqualThan(n);
            bottles.add(new Bottle(amount));
            n -= amount;
        }

        return bottles;
    }

    private static int getTwoSquareLowerOrEqualThan(int n) {
        int twoSquareNumber = 1;
        while(true) {
            if(n < twoSquareNumber) break;
            twoSquareNumber *= 2;
        }

        return twoSquareNumber/2;
    }

    private static int pouring(ArrayDeque<Bottle> bottles) {
        int cycleNumber = bottles.size() - K;
        int needBottle = 0;
        for (int i = 0; i < cycleNumber; i++) {
            Bottle smallAmountBottle = bottles.pollLast();
            Bottle largeAmountBottle = bottles.pollLast();
            needBottle += largeAmountBottle.amount - smallAmountBottle.amount;
            bottles.addLast(new Bottle(largeAmountBottle.amount * 2));
        }

        return needBottle;
    }
}

class Bottle {
    int amount;

    public Bottle(int amount) {
        this.amount = amount;
    }

    @Override
    public String toString() {
        return "Bottle{" +
                "amount=" + amount +
                '}';
    }
}