문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

정수 n이 주어졌을 때, 각 i(0 <= i <= n)에 대해 ans[i]가 i의 이진 표현에서 1의 개수인 길이가 n + 1인 배열 ans를 반환해라.

Example

#1
Input: n = 2
Output: [0, 1, 1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

#2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints

• 0 <= n <= 10^5

Solved

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        int sub = 1;

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

            dp[i] = dp[i - sub] + 1;
        }

        return dp;
    }
}