[백준] 1052 :: 물병

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

1052번: 물병

마치 구현인듯 보이지만 알고보면 수학인 문제 허허,,

 

 

예시를 들며 문제를 이해해보자.

 

N=3일경우

[1, 1, 1]  => [2, 1] 로 합칠 수 있다.

N=5일 경우

[1, 1, 1, 1, 1] => [2, 2, 1] => [4, 1]로 합칠 수 있다.

 

N= 9일 경우

[1, 1, 1, 1, 1, 1, 1, 1, 1] => [2, 2, 2, 2, 1] => [4, 4, 1] => [8, 1]로 합칠 수 있다.

 

결과적으로 2의 i승이 되는 물의 양으로는 물병을 얼마든지 합칠 수 있다,

1L로 남는 수가 합칠 수 없는 물병이 되는 것이다. 

 

이를 조금 더 수학적으로 풀어보면

N을 2진법으로 변환했을 때 1로 표현되는 수가 최대한 합치고 난 후 물병의 개수가 되는 것이다.

 

예를들어, 9을 2진법으로 변환하면 1001이고, 이는 9의 경우 두개의 물병으로 합칠 수 있음을 의미한다 (8L 1개, 1L 1개)

다른 예시로 7을 2진법으로 변환하면 111이고, 이는 7은 세개의 물병으로 합칠 수 있음을 의미한다. (4L, 2L, 1L 각각 1개씩)

 

 

그래서 우리는 N의 값을 ++해가면서 필요한 물병의 개수가 K개를 넘지 않는 최댓값을 찾으면 되는 것이다.

 

소스코드

 

https://github.com/kumakuma34/Algorithm/blob/master/BOJ/BOJ/1052%5B%EB%AC%BC%EB%B3%91%5D.cpp

kumakuma34/Algorithm

/*
    [1052]물병
*/
 
#include <iostream>
#include <math.h>
#include <queue>
using namespace std;
int n, k;
 
int getCount(int n) {
    int cnt = 0;
    while (n > 0) {
        if (n % 2 == 1) cnt++;
        n /= 2;
    }
    return cnt;
}
 
int main() {
    cin >> n >> k;
    int ans = n;
    while (1) {
        if (getCount(ans) <= k) break;
        else
            ans++;
    }
    cout << ans - n << endl;
}