[Baekjoon] 1094. 막대기 (비트마스킹)

문제

1094번: 막대기

처음 풀이

pop()으로 풀었는데, 우선순위큐를 활용하는 방식이 더 일반적인 것 같다.

arr = [64]
x = int(input())

while sum(arr) != x:
    if sum(arr) > x:
        target = arr.pop()
        arr.append(target//2)
        arr.append(target//2)
        if sum(arr[:len(arr)-1]) >= x:
            arr.pop()
        else:
            pass

    else:
        result = 1

result = len(arr)
print(result)

 

그런데 이 문제는 비트마스킹 문제로 한 줄로 답이 나오는 문제였다.

 

비트마스크

비트마스크란 이진수를 사용하는 컴퓨터의 연산 방식으로, 정수의 이진수 표현을 자료 구조로 쓰는 기법이다.

구현 방법 중 하나인 "원소의 포함 여부 확인" 을 보자.

 

" A 집합에 특정 원소가 포함되어 있는지 확인하는 방법이다. k번째 원소가 포함되어 있는지 확인하고 싶다면, k번째 bit가 켜져 있는지만 확인하면 된다. "

 

즉 문제에서 막대기가 64고 구하고자 하는 길이가 Xcm 이다.

X 가 64 라면 비트로 0b1000000

X 가 32 라면 비트로 0b100000

X 가 23 이라면 비트로 0b10111

이다.

 

비트마스크 각 자리는 10진수로 64 32 16 8 4 2 1  에 해당한다.

즉 몇 개의 막대를 풀로 붙여 X 로 만들 수 있는가? = X를 이진수로 표현했을 때 1이 몇개인가?

이다.

 

해당 원소가 포함되어 있다면 1, 없다면 0이기 때문이다.

 

따라서 문제는 X를 이진수로 바꾸고, 1의 갯수를 구해주면 된다.

bin() 함수로 이진수로 바꿔주면 문자열(str) 자료형으로 출력되고, count 메서드로 문자열 1의 갯수를 세주면 된다!

 

# 비트마스크 방식

print(bin(int(input())).count('1'))

 

 

 

참고

비트마스크 (BitMask) 알고리즘