백준 1052 : 물병 ( Python )

문제 링크

📌 사용 알고리즘 : bitmask , greedy , bruteforcing

완전탐색으로 푸는 방법부터 알아봅시다.

초기에는 물병이 1 L 씩 들어있습니다. 그리고 2개를 합치면 2 L 짜리 1개의 물병이 생깁니다.

절반씩 줄어드므로 물병을 합치는 과정은 $O(log(N))$ 의 시작복잡도가 듭니다.

import math
print(math.log2(10**7))

위 코드의 값은 23.253496664211536 입니다.

그렇다면 K 보다 물병의 개수가 작거나 같을때까지 물병을 하나씩 추가해보면 되지 않을까요?

시간복잡도는 $O(Nlog(N))$ 이므로 충분히 가능합니다.
따라서 dp 배열을 N 만큼 생성해주고 물병을 합치는 연산과 물병을 구하는 함수를 만들어 준다음에 물병을 하나씩 추가하면 구할 수 있습니다.

조금더 간단하게 생각해봅시다.
10진수 정수 1,2,3,4,5 를 생각해보면 2진수로 나타냈을때 0001,0010,0011,0100,0101 이 됩니다.

잘 보면 비트의 1의 개수가 물병의 개수가 됩니다.

따라서 $N$ 이상이면서 비트가 $K$ 개 이하인 최소값을 찾으면 답이 됩니다.

📌 코드

import sys,math
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

def find():
    i = 0
    count = 0
    while (1<<i) < len(dp):
        if dp[1<<i]:
            count+=1
        i+=1
    return count

def add():
    i = 0
    while 1<<(i+1) < len(dp):
        if dp[1<<i]:
            dp[1<<(i+1)]+=dp[1<<i]//2
            dp[1<<i]%=2
        i+=1

N,K=MI()
dp=[0]*(10**7+1)
dp[1] = N
answer = 0
while True:
    add()
    if find() > K:
        dp[1]+=1
        answer+=1
    else:
        break
if find() > K:
    print(-1)
else:
    print(answer)

import sys,math
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

N,K=MI() ; count = 0
while bin(N).count('1')>K:
    N+=1 ; count+=1
print(count)