[BOJ] 1052 - 물병

Sierra·2022년 1월 27일

[BOJ] Greedy

목록 보기

5/33

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

문제

지민이는 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을 출력한다.

예제 입출력

예제 입력 1
3 1
예제 출력 1
1
예제 입력 2
13 2
예제 출력 2
3
예제 입력 3
1000000 5
예제 출력 3
15808

Solution

#include <iostream>

using namespace std;

int countWater(int water){
    int count = 0;
    while(water > 0){
        if(water % 2 == 1) count++;
        water /= 2;
    }
    return count;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    int answer = 0;
    if(N <= K) {
        cout << "0\n";
    }
    else{
        while(1){
            if(countWater(N) <= K) break;
            answer++;
            N++;
        }
        cout << answer << '\n';
    }
}

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

조건에 주목하고 문제를 풀어야 한다.
어렵게 생각하면 끝도없이 어려운 수학문제다. coutWater 함수를 한번 주목해보자.

int countWater(int water){
    int count = 0;
    while(water > 0){
        if(water % 2 == 1) count++;
        water /= 2;
    }
    return count;
}

일단 N개의 입력이 들어왔다. N 개의 물병들 끼리 2개씩 우선 짝을 맞춘다고 치자.
그럼 누군가 짝이 안 맞는 1개가 반드시 생기게 되어있다. 어차피 숫자는 홀수 아니면 짝수 일 테니까.
그러면 그 놈만 하나 더 짝을 맞춰주면 될 것이다.
이제 짝을 맞췄던 놈들끼리 또 두 쌍씩 짝을 맞춘다. (물은 1 + 1 = 2가 되어있을 것이고 물병은 1개가 되어있을 것이다.) 그러면 또 누군가 남거나, 짝이 다 맞을 것이다.
이 과정을 마지막 1개가 될 때 까지 계속한다. 그러면 현재 상황에서 총 몇개의 물병이 나올 지를 확인할 수 있다.

13 2 입력이 들어 온 상황을 가정해보자.
우선 13은 2, 2, 2, 2, 2, 2, 1로 만들 수 있다. 13 / 2 = 6이고 13 % 2 = 1 이니까.
짝이 맞는 6개의 물병들은 각각 하나의 물병들이라고 생각할 수 있다. 그럼 이 물병들 끼리 짝을 맞추면 당연히 2, 2, 2 의 짝이 딱 떨어지는 상황이 될 수 있다.
자 이제 이 3개가 되어버린 물병들의 짝을 맞춰보자. 2, 1이겠지. 짝이 맞지않은 물병 하나가 또 생긴다.
마지막으로 1개의 물병에 대해 짝을 맞출 게 없다. 여기서 짝이 맞지 않은 물병들의 갯수가 이 상황에서 나를 수 있는 물병의 갯수다. 현재는 3개니까 K보다 큰 상황이다.

눈치가 빠른 사람은 이해할 수 있겠지만 문제의 조건 상 짝을 맞출 수 있는 경우는 2의 배수인 경우다. 그게 아니라면 1개의 짝이 맞지않은 경우가 생기고 그 녀석은 독립된 하나의 물병이다. 같은 양의 물이 들어있는 물병 두개를 모으고 모으고...이 과정을 그려보면 Binary Tree를 역으로 그려놓은 것 마냥 변한다. 실제로 그렇게 그려보면 답이 보인다.

실제로 N이 5일때 상황이다. 최종적으로 2개의 물병이 생긴다. K가 2라면 답이 되겠지만 만약 K가 3이라면 물병을 더 사와야 한다.