[Python] 비트마스킹 - 1094 막대기

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

1094번: 막대기

 

 

풀이

 

결론부터 말하자면 입력값을 2진수로 변환했을때 1의 갯수를 찾는 문제이다.

합이 X가될때까지 계속 2로 나누고 하나를 버려야하니 2진수로 표현하는 것과 같다.

물론 구현 방식으로도 풀 수 있다.

 

 

코드

 

1. 입력값을 binary로 바꿔서 1의 갯수 세기

 

X = int(input())
answer = 0
X = bin(X)
for x in X:
    if x == '1': answer += 1
print(answer)

 

 

2. collections의 Counter 사용 => 메모리도 더 많이 쓰고 시간도 더 느리다

 

from collections import Counter
X = int(input())
answer = 0
X = bin(X)
answer = Counter(X)['1']
print(answer)

 

 

3. 구현

 

정말 정직하게 문제서 하라는대로 했다 ㅋㅋㅋㅋ

 

def half(list):
    list.sort()
    min = list[0]
    list.append(min//2)
    return(list)


X = int(input())
sticks = [64]
count = 0
    
if sum(sticks) == X:
    count = 1
    
while sum(sticks) != X:
    if sum(sticks) > X:
        half(sticks)
        del sticks[0]
    else:
        half(sticks)
    count = len(sticks)
print(count)

 

위에 코드 보다는 조금 더 간단하게 짠 코드

 

X = int(input())
stick = 64
count = 0
while X != 0:
    if X >= stick:
        count += 1
        X -= stick
    else:
        stick = stick //2
print(count)

 

** 참고

 

bit(NUM) 하면 str 타입으로 반환한다

 

X = int(input())
X = bin(X)
print(type(X))

>> <class 'str'>