[백준] 1052번: 물병 (Python, 파이썬)

문제 링크: https://www.acmicpc.net/problem/1052

1052번: 물병

문제 이해:

 

이걸 어떻게 풀까 고민하다 생각이 도저히 안났다. 각각 다른 물의 양이 들어 있는 물병들을 어떻게 표현할지 감이 안왔다. dictionary를 써야하나 생각도 했지만, 음 이런 접근법이 아닌 것 같았다. 

고민하다 도저히 안돼서 다른 사람의 풀이를 찾아봤다. (참고)

 

Key point

N을 이진법으로 바꿔서 표현하면 되는 것이었다! 지금까지 안풀렸던 문제들의 풀이 중에 제일 놀랐던 풀이법이었다..

(이진법 관련 문제를 많이 안풀어서 그런가? 아무튼!!)

bin(n): n을 이진법으로 바꿔줌!

 

13을 이진법으로 바꾸면 ${1101}_{(2)}$ 이다. 즉 8L 1개 / 4L 1개 / 1L 1개로 만들 수 있다는 뜻이다!

그다음 물병을 하나 더 사면 (N=N+1) --> ${1110}_{(2)}$: 1L짜리를 하나 샀으니까 8L 1개 / 4L 1개 / 2L 1개를 만들 수 있는 것!

이런 식으로 할 수 있는 것이다! 정말 놀랍댜..

N, K = map(int, input().split())

res = 0

while bin(N).count('1') > K:
    N += 1
    res += 1
print(res)