FilesExpand file tree

 main

/

shinsj4653.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (38 loc) · 891 Bytes

 main

/

shinsj4653.py

Top

File metadata and controls

• Code
• Blame

52 lines (38 loc) · 891 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

"""

[문제풀이]

# Inputs

n: int

# Outputs

ans: arr

길이: n + 1

ans내 각 원소들 : ans[i]: i의 이진법에서 1의 개수

# Constraints

0 <= n <= 10^5

# Ideas

2중 for문 이면 안됨

[회고]

dp를 활용한 풀이도 같이 알아두자

"""

# 내 풀이

class Solution:

def countBits(self, n: int) -> List[int]:

ans = []

for i in range(n + 1):

if i == 0 or i == 1:

ans.append(i)

continue

num = i

cnt = 0

while num > 0:

num, n = num // 2, num % 2

if n == 1:

cnt += 1

ans.append(cnt)

return ans

# 해설

class Solution:

def countBits(self, n: int) -> List[int]:

dp = [0] * (n + 1)

for num in range(1, n + 1):

dp[num] = dp[num // 2] + (num % 2)

return dp