알고리즘/수학

[백준]1052 물병 #그리디

씩씩한 IT블로그 2020. 6. 17. 21:28
반응형

1. 풀이

(1) 물병의 개수가 a일때, 최대로 합칠 수 있는 개수를 반환하는 함수 cheak(a)를 만든다.

- 2로 나누었을 때 몫이 묶인 물병의 수가되고, 나머지가 묶이지 않은 물병의 수가된다.

(2) i는 N에서 시작하여 1씩 증가하면서 cheak(i)가 K이하가 되는 첫번째 수를 구한다.

- 그 수가 최소로 더 필요한(더 사야할) 물병의 수가 된다.

2. 소스코드

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

def cheak(num):
    ans=0
    while(1):
        a=num//2
        b=num%2
        ans+=b
        num=a
        if num==0:
            break
    return ans


if K>=N:
    print(0)
else:
    i = N
    while(1):
        if cheak(i)<=K:
            print(i-N)
            break
        else:
            i+=1
반응형