[Easy] 338. Counting Bits

 

int타입 n이 주어지면 n+1 길이의 int형 배열을 생성하고 이 배열의 i번 째 원소를 i를 이진수로 나타내었을 때 1의 개수로 채워서 반환하는 문제이다. 즉 3번째 원소는 3(0011)의 1의 개수인 2이다.

처음엔 그냥 쉽게 bitset 클래스를 이용하여 풀었는데, 분류가 DP로 되어 있어서 DP 풀이법을 봤더니 내 머리로는 생각도 못했을 방법이었다.

우선 bottom-up 방식으로 낮은 원소부터 채운다. 그리고 i번째 값은 두 부분으로 나누어서 구한다. 한 부분은 첫 번째 비트 부분이고 한 부분은 나머지 비트 부분이다.

예를 들어 i가 3일 경우, 3을 2로 나눈다. 2로 나누는 것은 1bit만큼 right shift 하는 것과 같다. 그러면 0011이 0001이 되고 이는 십진수로 1이다. 그럼 i가 1일 때 1의 개수는 앞에서 미리 구했을 것이다. 여기에 shift 하기 전 i(3)의 첫 번째 비트(1or0)을 더해주면 right shift한 수에서 구하지 못한 첫 번째 비트를 알 수 있다.

만약 i가 5일 경우 0101에서 1만큼 right shift한 0010의 1의 개수를 미리 구해둔 곳에서 가져오고(1) 여기에 0101의 첫 비트 1을 다시 더해주면 2가 된다.

첫번째 비트는 1과 & 연산을 하면 구할 수 있다. 따라서 다음과 같이 간단하게 구할 수 있다.

vector<int> countBits(int n) 
{
        const int size = n + 1;
        vector<int> mem(size, 0);

        for(int i = 1; i < size; ++i)
        {
            int part1 = mem[i >> 1]; // == mem[i/2]
            int part2 = i & 1; // i의 첫 번째 bit
            
            mem[i] = part1 + part2 ;
        }
        
        return mem;
}