[백준 1094] 막대기

문제
길이가 64cm인 막대가 있다. 이 막대기를 잘르고 붙여서 Xcm인 막대를 만들려고한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다.
막대는 다음과 같은 과정을 거쳐서 자른다.
1. 가지고있는 막대의 합이 X보다 크면 아래와 같은 과정을 반복한다.
1-1 가지고있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
1-2 위에서 자른 막대 중 하나가 X보다 크거나 가타면 자른 것중 하나를 버린다.
2. 남아있는 모든 막대를 풀로붙여서 Xcm를 만든다.
몇 개의 막대로 Xcm를 만들 수 있는지 구하라.

입력
첫째 줄에 64이하의 자연수 X가 입력된다.

출력
Xcm 만들기위해 몇 개의 막대가 필요한지 출력한다.

---

비트연산자를 활용하는 방법을 공부하였다. 이를 어떻게 활용할 수 있을지 알고리즘 문제를 풀면서 익혔다.

그 중 막대기라는 문제를 풀어보았다.

X를 입력받았을 때 이를 2진수로 표현하여 1의 개수가 필요한 막대기 수가 된다는 것을 알게되었다.

따라서 X를 2진수로 변환했을 때 1의 개수를 출력하도록 하였다.

 

구현

64는 1을 왼쪽으로 6번 밀었을 때나타난다. 그리고 입력되는 수가 64이하이기 때문에 0~6까지 왼쪽으로 시프트 연산자를 활용하여 1을 찾아내도록 한다. 만약 if문 부분이 참이라면 그 자리에 1이있다는 것이다. &연산은 두 개의 수가 모두 1이어야하기 때문이다.

N = int(input())
answer = 0
for i in range(7):
    if N & (1<<i):
        answer += 1
print(answer)