[알고리즘] 물병 백준 1052 python

문제 바로가기

풀이

그리디 문제 냄새가 난다.
예제입력 2를 살펴보면
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
= 8, 4, 1
더이상 물통을 합칠 수 없다.
상점에서 물통을 사면
8, 4, 1, 1
=8, 4, 2
더이상 물통을 살 수 없으므로
8, 4, 2, 1
한병 더 사면
8, 4, 2, 1, 1
= 16

위의 예제 입력에서 물병을 같은 무게끼리만 합칠 수 있다는 말은 2의 제곱승인 숫자들의 합으로 이루어져 있다는 것을 알 수 있다.
n을 2의 제곱승인 숫자들로 표현하는 것 중 가장 간단한 방법은 이진수로 바꿔 이진수에 있는 1의 개수를 세면 된다.
우리는 상점에서 물을 살 수 있으므로 최종 물병 수가 k보다 크게 되면 n에 1을 더해서 다시 이진수로 표현해서 1의 개수를 세면 된다.
그렇게 해서 이진수로 나타낸 n을 이진수로 표현한 것의 1의 갯수보다 k가 크거나 같아지면 그때까지 n에 더해준 수가 result가 된다.

import sys

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

count = 0;

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

print(count)