[백준] 1052 물병(비트마스킹) - Python

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

1052번: 물병

n, k = map(int, input().split())
ans = 0
while True:
    one_cnt = bin(n).count("1") # n이진수로 변환 후 1개수 세기
    if one_cnt > k: # 1개수가 더 많다면 
        n += 1 # n + 1 해주기
        ans += 1
    else:
        break
print(ans)

 

- 접근방식: 물을 합치려면 2의 배수들만 합칠 수 있으므로 이진수로 변환, 결국 이진수의 1의 개수가 다 합친 후 있는 물병의 개 수이다. 만약 현재 1이상의 물병이 k보다 많으면 새 물병을 가져와 다시 합쳐보기.

- 느낀점: 처음에 이진수를 이용하여 풀려 생각하지 못했다.. 그래서 그리디 느낌으로 구현하다 막혀서 솔루션을 참고해보니 이진수를 이용하여 쉽게 풀 수 있었다.