📃 문제 설명

Counting Bits

[문제 출처 : LeetCode]

👨‍💻 해결 방법

Dynamic Programming 태그에서 문제를 골랐는데, 문제를 보고 DP로 접근하기가 쉽지 않아서 갸우뚱했다.

0부터 n까지의 수를 비트로 표현했을 때 1의 개수를 세어 반환하면 되는 문제이다.

나는 말그대로 0부터 n까지의 수를 비트로 변환한 후 1의 개수를 세었다.
이 방법말고 다른 방법이 분명 있을 것 같다는 느낌은 있었지만 생각이 안났다...

제출 후 다른 풀이를 보며 경악을 금치 못했다..
아래 소스 코드에 내 풀이와 함께 인상깊은 코드를 주석으로 표시해두었다.

자주 들여다보면 비트에 대한 이해도가 깊어질 것 같고 비슷한 문제를 더 다양한 방법으로 접근할 수 있을 것 같다.
그럼 20000~

👨‍💻 소스 코드

class Solution:
    def countBits(self, n: int) -> [int]:
        res = []
        for i in range(n + 1):
            res.append(bin(i)[2:].count('1'))
        return res

    # def countBits(self, n: int) -> [int]:
    #     n += 1
    #     ans = [0, 1]
    #     while len(ans) < n:
    #         ans = ans + [1 + x for x in ans]
    #     return ans[:n]

    # def countBits(self, n: int) -> [int]:
    #     res = [0] * (n + 1)
    #     for i in range(1, n + 1):
    #         res[i] = res[i & (i - 1)] + 1
    #     return res