[n1094] 막대기 in python

 

합 > x

1. 가장 짧은 막대기를 절반으로 나눈 막대기를 리스트에 넣는다.

(원본 막대기는 삭제)

2. 리스트 오름차순으로 정렬

3. 가장 짧은 막대기의 절반을 제외한 나머지 합계가 x보다 크거나 같으면?

가장 짧은 막대기의 절반 하나를 제거한다. 

 

이 과정은 합==x일 때 종료

 

x=int(input())
array=[64]
while sum(array)>x: # 합>x
        # 1번
        min_value=min(array) # 가장 짧은 막대를 절반으로 나눈다.
        array.remove(min_value)
        array.append(min_value//2)
        array.append(min_value//2)
        array=sorted(array)
        if sum(array)-min_value//2 >=x:
            array.remove(min_value//2)
            continue
print(len(array))

---

위처럼 함수를 굳이 구현하지 않아도

이진수의 특성을 이용하면 풀 수 있는 문제였다.

 

x=23인 경우를 생각해보면,

23을 2진수로 바꾸면 10111

 

1*2^0+ 1*2^1 + 1*2^2+ 0*2^3+1*2^4

1+2+4+16

 

1,2,4,16 => 4개!!

 

print(sum(list(map(int, bin(int(input()))[2:]))))