[ 백준 1052 ] 물병 (C++)

백준의 물병(1052) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는, 같은 양이 들어있는 물병끼리 합칠 수 있을 때, 최대 몇 병의 물병을 더 사야, K개 이하로 물병을 만들 수 있는지를

   묻는 문제이다. 그렇다면 물병을 언제 합칠 수 있는지, 어떤 규칙이 있는지 먼저 한번 찾아보도록 하자.

   예를 들어서, 초기에 5통의 물병이 있다고 생각해보자. 최대 들 수 있는 물병의 갯수는 1개라고 가정하겠다.

   초기상태는 { 1, 1, 1, 1, 1 } 이 될 것이다. 여기서 일단 합칠 수 있는 물병을 모두 합쳐본다면

   { 2, 2, 1 } 이 될 것이다. 여기서 한번 더 합친다면 { 4, 1 } 이 될 것이고, 최대 1개밖에 들지못하므로, 물병을 하나 더 사야한다.

   하나를 더 사게되면, { 4, 1, 1 } 이 되고 합치면 { 4, 2 } 가 될 것이다. 이를 합치기 위해서 2개의 물병을 더 사서 { 4, 2, 2 } 로

   만든 후, { 4, 4 } → { 8 } 로 만들어주어야 비로소 이 모든 물병들을 다 들고 갈 수 있게 된다. 즉 3병의 물통을 더 사야되는

   것이다.

   실제 위의 설명을 코드로 돌려봤을 때의 결과값이다.

   그렇다면 규칙을 한번 찾아보자. 초기 상태인 5병의 물통에서, 물통을 하나도 사지 않았을 때, 최대로 물병을 합친다면 물병은

   2병의 물병으로 만들 수 있다. { 1, 1, 1, 1, 1 } → { 2, 2, 1 } → { 4, 1 }

   그렇다면 이제는 5병이 아니라 2병부터 차근차근 모두 합치면 몇 병으로 만들 수 있는지 알아보자.

   2병의 경우 { 1, 1 } → { 2 } 로 한병을 만들 수 있다.

   3병의 경우 { 1, 1, 1 } → { 2, 1 } 로 2병을 만들 수 있다.

   4병의 경우 { 1, 1, 1, 1 } → { 2, 2, } → { 4 } 로 1병을 만들 수 있다.

   5병의 경우 { 1, 1, 1, 1, 1 } → { 2, 2, 1 } → { 4, 1} 로 2병을 만들 수 있다.

   6병의 경우 { 1, 1, 1, 1, 1, 1 } →  { 2, 2, 2 } → { 4, 2 } 로 2병을 만들 수 있다.

   7병의 경우 { 1, 1, 1, 1, 1, 1, 1 } → { 2, 2, 2, 1 } → { 4, 2, 1 } 로 3병을 만들 수 있다.

   8병의 경우 { 1, 1, 1, 1, 1, 1, 1, 1 } → { 2, 2, 2, 2, } → { 4, 4 } → { 8 } 로 1병을 만들 수 있다.

   그렇다면 여기서, 우리는 하나의 특징을 찾아낼 수 있다. 2의 거듭제곱승으로 이루어진 병수에 대해서는 1병으로 만들 수

   있다는 것을 의미한다. 즉, 2의 거듭제곱승인 숫자가 N으로 주어진다면, K값에 상관없이 사야되는 병수는 0병이 될 것이다.

   왜냐하면 K는 자연수의 범위라고 했으므로 최솟값이 1이기 때문이다.

   또 하나의 특징은 / 2 와 % 2 연산을 통해서 알 수 있다. 다시 돌아가서, 5병일 때 주목해보자.

   5병 일때는 위에서 2병으로 만들 수 있다고 하였다. 5를 2로 나눠버리면 '2' 라는 값이 나오고 , %2 를 하게되면 1이라는 값이

   나오게 된다. 즉, 여기서 나온 '2'와 '1'의 의미는 5병을 합쳐서 2병과 합쳐지지 못한 1병 으로 만들 수 있습니다 를 의미한다.

   위에서 보면 { 1, 1, 1, 1, 1 } 에서 { 2, 2, 1 } 로 된 것을 확인할 수 있다. 여기서 5 / 2를 한 값인 2를 다시한번 2로 한번 더 연산을

   하게되면 2 / 2 = 1, 2 % 2 = 0 이 나오게 된다. 즉, "합쳐진 2병을 합쳐보면 1병과 합쳐지지 못한 0병으로 만들 수있습니다." 를

   의미한다. 여기서 1을 또한 2로 연산해주게 되면 2 / 1 = 0 , 2 % 1 = 1 로, "1병을 합쳐보면 합쳐진 0병과 합쳐지지 못한 1병으로

   만들 수 있습니다"를 의미한다.

   즉, 해당 병수를 2로 나누기 연산을 한 값은 합쳐진 병수를, %2로 모듈러 연산을 한 값은 합쳐지지 못하고 남은 병수들을

   의미한다. 그렇다면 우리는 어느 값에 주목해야 할까?? 우리는 합쳐지지 못하고 남은 병수들에 주목해야 한다.

   왜냐하면, 우리는 병을 최대한 합쳐서 K병 이하로 만들어 줘야되기 때문에, 애초에 합쳐진 놈들은 안합쳐질때까지 만들어주고

   남은 병수의 갯수만 Count 해주면 된다.

   7병으로 다시한번 이해해보자.

   7을 2로 나누기 & 모듈러 연산을 진행해보자. 7 / 2 = 3 , 7 % 2 = 1 이 된다.

   이 말의 의미는 " 7병을 합쳐진 3병과 합쳐지지 못한 1병으로 만들 수 있습니다." 가 된다. (현재 합쳐지지 못한 병수 = 1)

   합쳐진 3병에 대해서 연산을 진행하면, 3 / 2 = 1 , 3 % 2 = 1 이 된다.

   이 말의 의미는 "합쳐진 3명을 다시 합쳐보면 합쳐진 1병과 합쳐지지 못한 1병으로 만들 수 있습니다." 가 된다.

   (현재 합쳐지지 못한 병수 = 2)

   합쳐진 1병에 대해서 연산을 진행하면 1 / 2 = 0 , 1 % 2 = 1 이 된다.

   이 말의 의미는 "합쳐진 1병을 다시 합쳐보면 합쳐진 0병과 합쳐지지 못한 1병으로 만들 수 있습니다."가 된다.

   (현재 합쳐지지 못한 병수 = 3)

   즉, N이 7일 때, K가 3보다 더 작은 값이라면 물통을 더 살 필요가 있음을 의미한다.

   이런 과정을 N값을 계속해서 ++ 시켜주면서 반복해주어야 한다. 반복해 주면서, K보다 더 작거나 같은 값들이 나오면 비로소

   그 때, "합쳐지지 못한 병수들도 K병 이하이기 때문에 모두 들고 갈 수 있습니다" 를 의미하게 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N, K, Answer;
 
void Input()
{
    cin >> N >> K;
}
 
int Add_Water(int x)
{
    int Cnt = 0;
    while (x > 0)
    {
        //5면
        // 2가 되고 -> 1이되 
        if (x % 2 == 1) Cnt++;
        x = x / 2;
    }
    return Cnt;
}
 
void Solution()
{
    if (N <= K) cout << 0 << endl;
    else
    {
        while (1)
        {
            int Temp_Result = Add_Water(N);
            if (Temp_Result <= K) break;
 
            Answer++;
            N++;
        }
        cout << Answer << endl;
    }
 
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}