백준 1052번 물병 | python | 비트마스킹

문제

링크

풀이

이진수로 바라보고 풀어야하는 문제이다. 이것만 깨달으면 답은 매우 쉽게 찾을 수 있다.

문제를 보다보면 이진수로 문제를 해결해야겠다는 감이 오는데
물의 양이 1, 2, 4, 8, 16, ... 이렇게 2의 제곱 형태일 때만 합칠 수 있다는 점과, 애초에 입력이 매우 크다는 점 때문이다.

먼저 문제를 보면 물을 재분배하는 제약이 존재한다. 무조건 '같은 수'를 더할 수 있다는 것이다. 이진수로 보면

100(2)+100(2)=1000(2)

예제2를 통해 값을 어떻게 구해야할지 이진수 관점에서 규칙을 도출해내보자.
N = 13, K=2 일 때

• 초기 물병 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
• 물병 합 2, 2, 2, 2, 2, 2, 1
• 물병 합 4, 4, 4, 1
• 물병 합 8, 4, 1

물병은 3개가 된다.
13을 이진수로 바꾸면 1101 이다.

결국 1의 개수가 다 합쳤을 때의 물병의 개수가 됨을 알 수 있다.
우리는 이 1의 개수를 K 아래로 떨어뜨리고 싶기 때문에 물병을 1의 개수가 K 이하가 될 때까지 물병을 계속 더해가면 된다

전체 코드는 아래와 같다

import sys

input = sys.stdin.readline

n, k = map(int, input().strip().split())

count = 0
while bin(n).count("1") > k:
    n += 1
    count += 1
print(count)

그런데 여기서 추가로 생각해볼 만한 점이 있는데,
1을 더할 때 0이 있는 자리에서 1을 더하는 행위는 1이 줄어드는 것이 아니라 오히려 늘어나게 한다는 점이다. 따라서 왼편에서 오른쪽으로 비트에 접근하면서 1이 최초로 등장하는 자리에 1을 더해준다면 1이 줄어들게 만들 수 있으며 또한 불필요한 연산을 줄일 수 있다. 해당 코드는 아래와 같다.

n, k = map(int, input().split())
answer = 0
while bin(n).count('1') > k:
    idx = bin(n)[::-1].index('1') # 1이 오른쪽에서 몇 번째에 있는지 찾기
    answer += 2 ** idx # 2 ^ (idx) 만큼 더하기
    n += 2 ** idx # 2 ^ (idx) 만큼 더하기
print(answer)

아래 사진을 보면 확실히 시간이 훨씬 단축되었다!
아직 잘 이해가 가지 않는다면 해당 포스팅을 참고해보자.

아 그리고 또 하나 생각할 점은
문제에서 정답이 없을 경우에는 -1을 출력한다 라고 되어있는데, 사실 물병에 들어갈 수 있는 물의 양은 무한정이고 상점에서 살 수 있는 물병의 개수 또한 제한이 없기 때문에 사실상 정답이 없는 상황은 애초에 존재하지 않는다. 따라서 해당 부분에 대한 조건은 생각할 필요가 없다.

보통 항상 예외가 존재한다고 명시되어있으면 무조건 처리해야한다고 생각했는데 꼭 그렇지도 않다는 것을 깨달았다. ㅎ;