리트코드 338. Counting Bits c++ // 1의갯수세기, dp, 비트

https://leetcode.com/problems/counting-bits/description/

1. 비트 구현 풀이

1. 각각 숫자에대해 

2진수를 구하면서 1의 갯수를 계산한다.

O(n lgn)

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret;

        for(int i=0;i<=n;++i){
            int cnt=0;
            int num=i;
            while(num){
                if(num%2==1) cnt++;
                num/=2;
            }
            ret.push_back(cnt);
        }
        
        return ret;

    }
};

 

2. dp풀이

*행동영역 : n이 홀짝일때를 나눠서 규칙을 발견해라!

n==0인 기저사례 처리 주의.

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1,0);
        if(n==0) return dp;

        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;++i){
            if(i%2==0){
                dp[i]=dp[i/2];
            }
            else{
                dp[i]=dp[i/2]+1;
            }
        }
        
        return dp;
        
    }
};