#338 (Easy)

어떤 자연수 N을 2진수로 나타낼 때 2로 계속 나눈 몫과 나머지를 이용해서 쉽게 나타낼 수 있다.

2진수로 나타내는 과정을 고려하면 아래와 같은 등식이 성립한다.

countBits(N) = countBits(2N)
countBits(N)+1 = countBits(2N+1)

1. Brute Force

제시된 n에 대해 1부터 n까지 for-loop을 돌면서 2진수로 변환한 뒤 bit 1의 개수를 세어 result = []로 return 하는 방법이다.

시간 복잡도: O(NlogN)

2. Dynamic Programming

countbits(N) = countbits(2N) 의 관계를 이용하여 result를 완성하는 방법이다. 작은 문제들을 저장하고 이를 이용하여 큰 문제를 해결하는 방법이다.

Dynamic Programming 을 활용한 문제 풀이 방법이다.

시간 복잡도: O(N)
Iterate through the range of numbers once.
Space: O(n)
We use a num-sized array.

class Solution(object):
    def countBits(self, n):
        dp = [0 for i in range(n+1)]
        for i in range(1,n+1):
            dp[i] = dp[i>>1] + (i&1)
        return dp