[백준-파이썬] 비트 마스크 문제들

흑흑.. 스터디에서 누군가 비트 마스크 문제를 넣었는데, 전--혀 못 풀겠다.
하긴 나는 지금까지 백준에서 비트 마스크 문제를 단 하나밖에 안 풀었다..;;
그래서 쉬운 문제부터 풀려고 한다!

(미완성입니다.ㅠ)

 

1094. 막대기

https://www.acmicpc.net/problem/1094

이건 비트 연산을 바로 쓴다기 보다는 비트를 이해하고 있나? 그런 문제 같다!
좀 생각해보면 이 숫자에서 2의 제곱수가 몇개 들어있나를 구하는 문제라는 걸 알 수 있다.
bin()을 이용해서 풀었다.

import sys

input = sys.stdin.readline

X = int(input())
binary_X = bin(X)
print(binary_X.count('1'))

14936. 엘리베이터 장난

1052. 물병

https://www.acmicpc.net/problem/1052

같은 양의 물병 두개를 고르고, 하나의 물병의 물을 다른 쪽에 다 붓는다. -> 2의 제곱 수와 관련 있다는 느낌..(?)을 받으면 된다.. 사실 나도 스터디에서 다른 분 풀이를 들었다..ㅎㅎ
이걸 좀 더 생각하면, 처음에 가진 N개의 물병을 최대한 줄였을 때 몇 개가 되는지 알 수 있다. bin(N)을 하고, 거기에서 '1'의 개수를 세면 된다.

물병이 K개 이하가 될 때까지 줄여야 한다.
물병 수를 줄이려면 어떻게 해야 할까?
상점에서 물을 더 사와서, 이미 있는 물병의 물과 같은 양을 만들어서 합쳐야 한다. 그러면 물병을 하나 줄일 수 있으니까..~~
사야 하는 물병의 최솟값을 구하는 거니까, 최대한 적게 사는 게 좋다. -> N에서 2의 제곱수 중에서 자릿수 젤 낮은 것만큼 산다.

물병을 계~속 하나 더 사와서 합치고 합치고 하면 되니까, 정답이 없는 경우는 없다. K는 자연수니까..!(최소 1이라는 것)

import sys

input = sys.stdin.readline

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

n = N
final_water_cnt = 0

while bin(n).count('1') > K:  # 물병이 K개 이하가 될 때까지
    tmp = bin(n)
    # 최소 물 양 구하기 -> 그만큼 물 구입하기
    # 물을 합치기 (젤 낮은 자릿수에서 2의 배수였던 것을 그 다음 자릿수로 올림)
    idx = len(tmp) - tmp.rfind('1') - 1

    final_water_cnt += (1 << idx)

    n = n + (1 << idx)

print(final_water_cnt)

1322. X와 K