[백준 1052] 물병

[ 백준 1052 : 물병 ]

N개의 물병으로 K의 물병을 만드는 문제.
조건은 물을 합칠때는 같은 양의 물이 들어있어야한다.

처음있는 N의 물병으로 만들 수 있는 물병 갯수를 생각해본다.

예로 들어서 18개의 물병이 있다고 해보자.
N = 18 일 때 물병의 경우의 수를 보면,

이렇게 볼 수 있다.
그럼 총 18개부터 2개까지 물병을 사지 않고 가능하다는 말이다.

무조건 같은 양의 물병만 합칠 수 있으므로 1 -> 2 -> 4 -> 8 .... 모두 2의 제곱수이다.
그럼 N을 2의 제곱수로 나타내어보면
18 = 16 + 2 이다.
그럼 이진수로 생각할 수도 있다. 이진수로 18을 나타내어보면
10010(2)  이런식으로 표현 할 수있다.

이말은 이진수로 나타내었을때 1의 갯수가 물병의 갯수이고 이 1의 갯수가 K보다 작다면 어떻게든 N을 K로 물병을 더 사지 않고 만들 수 있다는 말이다.
N이 1000만 이하의 자연수 이므로 N을 1씩 더해주면서 이진수로 나타내었을때 1의 갯수가 몇 개인지 보면서 K개 이하로 나온다면 몇 번이나 더했는지를 출력해주면 된다.

여담이지만 한 번 틀렸는데
내가 이상한건가 입력이 18 23 이런식으로 나온다면 답이 5가 나와야되지 않나? 입력에서 K가 N보다 작다는 말이 없어서 N<K일때는 K-N이 답으로 나오게 하고 제출했더니 틀렸다...;; 알고보니 한 번에 K개 이하의 물병을 들 수 있으니 N이 K보다 작을땐 그냥 그대로 가져가면 되는거였다. 혹시나 나와 같은 이런 생각을 하신분들이 있을까봐.. ㅎ.