338. Counting Bits

[문제 접근법]

- 1부터 n까지의 숫자에서 각 숫자를 이진수로 변화했을 때 1의 개수를 찾는 문제이다. 

나는 1부터 n까지 각 숫자들의 패턴을 찾으려고 노력하였다. 총 2가지로 구현하였는데 코드 보면서 상세히 설명하겠다.

 

그림 1 - Counting Bits 예시 및 설명

 

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

Counting Bits - LeetCode

---

[구현 1] 

- DP의 Top-Down 방식으로 구현하였다.

F(n)=F(n/2) + n%2라는 일반항을 찾을 수 있다. 

 

  public int[] countBits(int n) {
        int []answer=new int[n+1];

        for (int i = 0; i <= n; i++) 
            answer[i]=answer[i >> 1] + (i&1);
        
        return answer;
    }

 

[구현 2] 

 - n이 2, 4 ,8 16 ... 2의 제곱 수를 기준으로 F(n)=F(n - 2의 제곱수) +1의 일반항을 구할 수 있음

public int[] countBits(int n) {
        int []answer=new int[n+1];
        int offset=1;

        for (int i = 1; i <= n; i++) {
            if(offset*2 == i)
                offset*=2;

            answer[i]=answer[i-offset]+1;
        }
        
        return answer;
    }