[백준 1052] 물병

문제

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

1052번: 물병

---

아이디어

한 쪽 물병에 담긴 물을 나머지 모두 붓기 때문에 물병에 있는 물은 2의 거듭제곱(2^x) 으로 표현할 수 있다. 

 

K개를 넘지 않는 이라는 표현이 핵심이다. 가능하면 x가 큰 물병이 많은 게 좋다는 뜻이다. 

1026개의 물병이 있었다고 해보자. 이 때는 2리터짜리 물병 513개보다는 1024리터짜리 물병 하나와 2리터짜리 물병 하나가 좋다는 뜻이다. (그렇다고 무조건 적은 것을 찾는 게 아니라, 이렇게 x가 큰 물병 위주로 만들어서 k개 이하의 물병만 나오면 된다.)

 

주어진 n을 2의 거듭제곱으로 나타내는 효과적인 방법이 있다. bin(n)을 이용하는 것이다. 

예를 들어, 1026은 다음과 같이 표현할 수 있다.

bin(1026)
> '0b10000000010'

1024리터(2^10)짜리 물병 하나, 2리터(2^1)짜리 물병 하나의 합이라고 생각할 수 있다.

 

지금 생각해보면 당연하지만 헷갈릴 수 있는 고민을 했었다. 

1. 같은 용량을 가진 물병이 하나씩만 있어야 하는가? > O

1024리터짜리 물병이 두 개가 있다고 가정하면, 두 개를 합쳐서 2048리터짜리 물병 하나로 만들어버리면 되기 때문이다.

 

이제 남은 과정은 어렵지 않다. 

1의 개수가 물병의 개수이다. 물병을 하나씩 늘려가면서 1의 개수가 k이하가 되는 순간을 찾으면 된다. 

몇 개를 추가했는지를 확인하기 위해 cnt 변수를 사용했다. 

 

n이 커지다보면 큰 물병 여러 개가 만들어지면서 k개 (또는 k개 이하)의 물병이 만들어지는 순간이 있다. 

 

2. k개로 줄이지 못하는 경우는 없는가? > O

한 개씩 추가하다가 2의 거듭제곱이 되는 순간 1개의 물병으로 만들 수 있게 된다. 

---

Solution

n, k = map(int, input().split())

cnt = 0
while bin(n).count('1') > k : 
    n += 1 
    cnt += 1

print(cnt)