첫 시도가 실패한 이유
일단 비트 마스킹을 사용하지 않아서 시간과 메모리를 많이 차지했다.
두번재로 똑같은 로직을 비트마스킹으로 코딩했을 때는 while문에 올바른 범위를 주지 않아서 틀렸다.
사용한 개념
비트마스킹
그리디
문제
지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.
물은 다음과 같이 재분배 한다.
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.
이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.
예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.
입력
첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.
예제 입력
1000000 5
예제 출력
15808
문제 검토
N의 범위가 10의 7제곱이다.
범위가 어마어마하게 크다.
이럴 때는 비트마스킹을 떠올려야 한다.
또한 나눌 수 있을 때 2로 나누고 1이남을때마다 물병을 사는 것에서 그리디 기법이 사용된다는 것을 알 수 있다.
풀이(python)
Python - 1
n, k = map(int, input().split())
cnt=0
A=1
while(N>K):
R=N%2
cnt+=R*A
A*=2
N//=2
N+=R
print(cnt)
처음 풀었던 풀이이다.
비트 마스킹을 사용하지 않았다.
Python - 2
n,k=map(int,input().split())
check = 0b000000000
cnt=0
while N>K:
if N%2==1:
check |= (1<<cnt)
N+=1
N/=2
print(cnt,check)
cnt+=1
print(check)
비트마스킹을 공부하고 비트마스킹으로 바로 구현해본 로직이다.
어디선가 틀리고 있는데 감을 잡기 어려웠다.
Python - 3
import sys
n, k = map(int, input().split())
count = 0;
while bin(n).count('1') > k:
n +=1
count +=1
print(count) 결국 풀이를 보고 작성한 코드이다.
N을 줄여나가는 것이 아니라 오히려 N에 1을 더하고 있다.
N에 1을 더해가다 보면 K가 물병의 개수와 관련 있는 bin(N)의 1의 개수와 같거나 커질 때가 온다.
아래 그림을 보자
13 2 예시의 동작 과정을 표로 만들어봤다.
마지막 반복에서 1의 개수가 2인 k보다 작아졌다.
물병개수는 총 3개임을 알 수 있다.
총평
비트마스킹은 중요도가 낮은 만큼 매우 어렵게 느껴졌다.
그리디 기법을 사용해서 로직을 구현하는 것은 어렵지 않았지만 구현을 완성시키기에는 어려웠다.
풀이를 보니 풀이를 보기 잘했다는 생각이 드는 문제였다.
비트마스킹에 시간을 너무 쏟지 말고 이 문제의 그리디스러운 부분에 집중하는 것이 좋을 것 같다.
