[leetcode 338] Counting Bits

주어진 num까지 각각의 숫자를 이진수로 변환시켰을 때 1의 개수를 기록한 배열을 return

Example 1:

Input: 2 Output: [0,1,1]

Example 2:

Input: 5 Output: [0,1,1,2,1,2]

 

ex2에서 0부터 5까지 각각을 이진수로 변환 0, 1, 10, 100 ... 그 때 1의 숫자를 세서 배열에 저장한다.

 

풀이

- dp

- dp 치곤 쉬웠다.

- 표를 적다보면 규칙이 발견된다.

0	1	2	3	4	5	6	7	8	9	10	11	12
0	1	1	2	1	2	2	3	1	2	2	3	2

1)2의 제곱수는 무조건 1이다.

2) 2의제곱수 사이에 있는 수는( 2<3<4)

예를 들어 3의 경우 dp[2] + dp[1]이다.

10의 경우 dp[8] + dp[2]이다. 즉 i보다 작은 가장 가까운 2의 제곱수 n에 대해 dp[i] = dp[n] + dp[i-n]이다.

 

start라는 2의 제곱수를 두고 num의 구간을 파악한다.

 

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp;
        
        dp.push_back(0); //0
        if(num ==0) {
            return dp;
        }
        
        dp.push_back(1); //1
        if(num == 1) {
            return dp;
        }
        
        int start = 2;
        for(int i=2; i<=num; i++){      
            if(i == start){
                dp.push_back(1);
                start *=2;
            }else {
                int base = start/2;
                dp.push_back(1+dp[i-base]);
            }
        }
        return dp;
    }
};