search

seungriyou / algorithm-study

알고리즘 & SQL 문제 풀이 기록
https://leetcode.com/u/summer_y
0 stars 0 forks source link

[LC] 338. Counting Bits #94

Open seungriyou opened 3 months ago

seungriyou commented 3 months ago

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

Approach

규칙이 존재하므로, 이에 따라 구간을 나누어서 생각한다.

[ 0 ~ 1 ]
bin(0) = 0
bin(1) = 1

[ 2 ~ 3 ]   -> offset = 2
bin(2) = 10 = 10 + bin(0)
bin(3) = 11 = 10 + bin(1)

[ 4 ~ 7 ]   -> offset = 4
bin(4) = 100 = 100 + bin(0)
bin(5) = 101 = 100 + bin(1)
bin(6) = 110 = 100 + bin(2)
bin(7) = 111 = 100 + bin(3)

[ 8 ~ 15 ]  -> offset = 8
bin(8) = 1000 = 1000 + bin(0)
...
bin(15) = 1111 = 1000 + bin(7)

다음과 같이 dp 식을 세울 수 있다.

offset = 1

for num in range(1, n + 1):
    if offset * 2 == num:
        offset *= 2

    dp[num] = dp[num - offset] + 1


Complexity