1052: 물병

시간 제한	메모리 제한
1초	512MB

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

 

입력

첫째 줄에 N과 K가 주어진다. N은 10⁷보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

 

---

풀이

같은 양의 물을 담고 있는 두 물병만 합칠 수 있다는 점이 이 문제를 해결할 키가 된다. 처음 봤을 때는 '3+3도 되고 5+5도 되고 다양한 방법이 가능하겠구나'라고 생각했는데 따져보면 물은 처음에 1L씩만 담겨있고, 이후에 같은 양의 물병끼리만 합치게 된다면 만들 수 있는 물병은 1L, 2L, 4L, 8L, 16L 등 2의 거듭제곱 꼴의 형태를 보이게 된다.

 

그래서 13개의 물병이 주어진 경우, 새로운 물병을 사지 않고 물병의 수를 최소한으로 줄인다면 아래 그림과 같이 줄일 수 있을 것이다. 줄이고 보면 8L, 4L, 1L의 물병이 남는데, 이것은 13을 이진수로 표현한 1101₍₂₎로 표현 가능하다. 따라서 N이 주어졌을 때, 물병을 사지 않고 최소한의 물병으로 줄인다면 이진수로 표현한 N에서 1로 표현된 자리만 세어보면 된다.

 

그럼 어떤 1들을 합쳐서 줄여주는 것이 좋을까. 단순하게 앞쪽(자릿값이 높은 곳)에서 줄이는 방법과 뒤쪽(자릿값이 낮은 곳)에서 줄이는 방법이 있다. 물병이 13개일 때 이 물병을 1개로 합치는 과정을 비교한 결과는 아래와 같다.

큰 것부터 합치게 되는 경우, 불필요하게 32L 물병까지 만들어지게 된다. 그렇다면 작은 것부터 합쳐주는 것이 좋다.

 

다시 정리해보면 이렇다. N이 59이고, 지민이가 들 수 있는 물병의 수 K가 3이라면 상황은 아래와 같이 정리된다.

59=111011₍₂₎이므로 총 5개의 물병으로 줄여질 수 있다. 여기서 2개의 물병을 합쳐서 없애야 하는데, 자릿값이 낮은 1의 자리와 2의 자리의 1을 앞으로 넘겨 8의 자리로 합쳐주어야 한다.

 

그럼 부족한 물병의 수는 다음 물병이 갖고있는 값에 대한 보수(어떤 수를 만들기 위해 부족한 수)로 생각할 수 있다.

 

단, 주어진 물병이 충분히 K를 만족할 수 있는 상황인 경우, 이 계산을 할 필요가 없다.

 

정답 코드

N,K=map(int,input().split())
bottles = []
water = 1

# 이진수로 변환하기
while N > 1:
    if N%2 == 1:
        bottles.append(water)
    N//=2
    water*=2
bottles.append(water)

# 필요한 물병 계산하기
if len(bottles) <= K:
    print(0)
else:
    for _ in range(K-1):
        del bottles[-1]

    for i in range(len(bottles)-1):
        bottles[-1] -= bottles[i]

    print(bottles[-1])

귀찮아서 구현을 안했지만 이 문제 비트마스크로 구현하는 것이 훨씬 깔끔하고 빠르다.

우에서 좌로 비트를 밀어가며 갯수를 세고, 마지막 K번째로 큰 물병을 확인한 순간부터 그 아래로 비어있는 비트를 모두 더해주고 마지막으로 1을 더해주면 필요한 물병의 양이 나온다.