[1스4코2파] # 169. LeetCode Pattern 338. Counting Bits

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (169차)
[4코1파] 2023.01.13~ (161일차)
[1스4코1파] 2023.04.12~ (72일차)
[1스4코2파] 2023.05.03 ~ (51일차)

Today :

2023.06.21 [169일차]
LeetCode Patterns
338. Counting Bits
https://leetcode.com/problems/counting-bits/

338. Counting Bits

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

문제 설명

문제 풀이 방법

n이 주어질 때, 1부터 n까지 켜진 비트의 수를 구함
O(N) 안에 풀어야 함! DP + bit 연산으로 푸는 문제

여기서 dp[n]: n이 켜진 비트의 수이다.
dp[0]은 0, 2진수로 표현하면 0000 => 비트의 값이 1인 것이 없음
dp[6]은 2진수로 0110 => 비트의 수가 2개
2^1 인 비트와 2^2인를 표현하는 것이 켜져있어서 2개
여기서 2^1을 표현하는 bit를 끄면 0100으로 10진수로 표현하면 4
(6에서2를 뺀 것)

즉, 자연수 6에서 가장 마지막으로 켜져있는 bit를 찾는다
6이 n이라면 -n은 1..1010 으로 표현 할 수 있고 이를 and 연산으로 하면 0010이 나옴.
즉 n이 6일 때 x&(-x)는 2가 나옴

dp 식은 dp[n] = dp[n-n&(-n)]+1

내 코드

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0]

        for i in range(1, n+1):
            dp.append(dp[i&(i-1)]+1)
        return dp

증빙

여담

비트 몰?루? dp 몰?루?