[백준 - 1052] 물병 - Java

문제 설명

 

1052번: 물병

 

접근 방법

해당 문제에서는 N개의 물병을 재분배하면서 최종적으로 남은 '비어있지 않은' 물병이 K개 이하일 경우 (나머지는 모두 빈 물병) 상점에서 최소한으로 산 물병의 개수를 요구하고 있습니다.

 

그렇다면 N개의 물병을 재분배하는 과정을 먼저 살펴보겠습니다.

 

우선 N = 1일 때는 K가 1이든 1000이든 (K의 값은 최소 1, 최대 1000) 항상 K 이하이므로, 상점에서 추가로 상점에서 물병을 사올 필요가 없습니다.

 

 

N = 2일 때는 최초 물병의 용량은 1L씩 채워져있다고 했으므로 하나의 병에 있는 물을 다른 하나의 병으로 모두 옮기면 물이 차있는 병 1개, 비어있는 병 1개가 남게 되는데, 위에서와 마찬가지로 K가 1이든, 1000이든 상점에서 물병을 추가로 사올 필요가 없습니다.

 

 

이때 N = 4, N = 8, ... 등 N이 2의 거듭제곱수일 경우는 위 작업을 반복적으로 해주면 마찬가지로 K의 값에 상관없이 결과값은 항상 0이라는 것을 알 수 있습니다.

 

 

이번엔 N = 3일 때를 고려해보겠습니다. 이때는 물병 3개를 각각 A, B, C라고 해보겠습니다. 마찬가지로 각각 1L 용량의 물이 차있을텐데 먼저 A를 B에 물을 다 넣고나면 A는 빈병, B는 2L, C는 1L로 비어있지 않은 병이 최종적으로 2개가 됩니다. 모두 다른 용량으로 차있기 때문에 더이상의 재분배는 불가능하므로 K는 적어도 2 이상이어야 합니다.

 

 

이때 K가 1이라면 어쩔 수 없이 물병(1L) 하나를 상점에서 사와야 합니다. 상점에서 사온 이 물병을 D라고 해보겠습니다. N = 3이었지만 이젠 N = 4 입니다. 물병 C의 물 1L를 모두 물병 D에 부으면 C는 0L, D는 2L가 되고 D의 용량과 B의 용량이 2L로 같게 되어 다시 하나의 물병에 물을 몰아 넣으면 4L 물병 하나만 남게 되고 나머지는 모두 빈병이 됩니다. 상점에서 하나의 물병만 샀으므로 K = 1 이하 조건을 충족합니다.

 

---

 

이제 이러한 접근 방법을 문제에 적용해보겠습니다.

 

우선 물병 2개를 골라 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는(재분배) 행위는 물병의 개수(N)에서 2로 나누는 것과 의미가 같다고 볼 수 있습니다.

 

최초 N개의 물병은 1L로 초기화되어 있습니다. 이때 주어진 물병을 2개씩 짝지어 하나의 쌍으로 만들면, 하나는 2L로, 하나는 0L가 됩니다. 예를 들어, 최초 6개의 물병이 있었다면, 2개씩 짝지어져서 2L의 물병이 3개가 되는 것입니다. 이렇게 재분배되어 새롭게 생긴 물병을 'N에서 2로 나눴을 때의 몫(6 / 2 = 3)'이라고 볼 수 있겠습니다.

 

이후에는 N 대신 이렇게 새롭게 생긴 물병에서 2를 나누어주는 작업(재분배)을 반복합니다. 최종적으로 몫이 0이 되면, 분배할 수 있는 물병이 더이상 존재하지 않게 됩니다.

 

            int Bottle = n;

            while (true) {
                // ...

                Bottle /= 2;
                if (Bottle == 0) break;
            }

 

하지만 물병의 개수가 홀수라서 2로 떨어지지 않는 경우(나머지가 1인 경우)도 있습니다. 앞서 6개의 물병을 재분배한 결과로 2L의 물병이 3개가 되는데, 이때 2개의 물병은 짝지어지지만 나머지 1개의 물병은 짝지어지지 못합니다. 이 물병은 앞으로 재분배됨으로써 새롭게 생기는 물병과 용량이 같아질리가 없으므로 최종적으로 비어있지 않은 물병(2L)으로 남아있을 것입니다.

 

이는 'N에서 2로 나눴을 때의 나머지(3 % 2 = 1)'라고 볼 수 있는데, 이처럼 나머지 1이 발생하는 경우는 물병의 개수를 2로 나누는 과정에서 여러번 발생할 수 있습니다. 그리고 그 빈도수는 최종적으로 비어있지 않은 물병이므로 'K개 이하'여야 합니다. K개 이하 조건을 충족하지 못한다면 상점에서 물병을 추가로 하나 사와야 합니다.

 

이렇게 상점에서 사온 이후에는 최초 N개의 물병에 1개의 물병을 추가하여 다시 재분배하는 작업을 반복적으로 수행해야합니다. 이러한 작업은 최종적으로 비어있지 않은 물병이 'K개 이하'일 때까지 계속 해주어야하며, 조건을 충족시켰을 때 그동안 상점에서 샀었던 물병의 개수를 반환해주도록 합니다.(문제 해결)

 

        int buyCnt = 0;

        while (true) {
            int remainingBottle = 0;
            int Bottle = n;

            while (true) {
                if (Bottle % 2 == 1) remainingBottle++;

                Bottle /= 2;
                if (Bottle == 0) break;
            }

            if (remainingBottle <= k) break;
            n++;
            buyCnt++;
        }

        System.out.println(buyCnt);

 

소스 코드

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

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()), k = Integer.parseInt(st.nextToken());

        if (n <= k){
            System.out.println(0);
            return;
        }

        int buyCnt = 0;

        while (true) {
            int remainingBottle = 0;
            int Bottle = n;

            while (true) {
                if (Bottle % 2 == 1) remainingBottle++;

                Bottle /= 2;
                if (Bottle == 0) break;
            }

            if (remainingBottle <= k) break;
            n++;
            buyCnt++;
        }

        System.out.println(buyCnt);
    }
}

 

참고자료

• https://www.acmicpc.net/problem/1052
• https://jaimemin.tistory.com/1511