[알고리즘] 물병 백준 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)
Author And Source
이 문제에 관하여([알고리즘] 물병 백준 1052 python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kcs05008/알고리즘-물병-백준-1052저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)