[S5] 1094. 막대기

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

1094번: 막대기

짱이다. 비트마스킹 알고리즘의 기초 문제라고 볼 수 있다. 지림..

비트마스킹의 글을 참고하면 더욱 도움 될 것이다.

https://jhcard.tistory.com/81

[알고리즘] 비트마스킹

이 문제를 통해 작성한 코드를 기반으로 아마 다른 문제를 응용해서 해결할 수 있을 것이다. 이전에 작성했던 문제들도 이와 같은 이론이 적용된다.

그러니까 주어진 X를 2진수로 변형하면 쉽게 알 수 있다.

23을 X로 주어졌다고 하자. 이것을 2진수로 만들면

10111이 된다.

우리는 막대기를 64 / 32 / 16 / 8 / 4 / 2 / 1cm짜리로 23을 만들어야 한다.

어떻게 만들어야 할까? 바로 16 / 4 / 2 / 1로 만들어야 한다.

익숙하지 않은가?

10111과 16 / 4 / 2 / 1

바로 23의 1의 개수가 답이 되는 것이다. 

이것을 코드로 풀어쓰면 다음과 같이 된다.

#include <cstdio>

int main(void){
    int X; scanf("%d", &X);
    int count = 0;
    while(X){
        if(X & 1) count++;
        X >>= 1;
    }
    printf("%d", count);
}