[백준 1094 / Python] 막대기

막대기

🔍 알고리즘 분류

• 수학

💡 문제 풀이

문제해석: 64, 32, 16, 8, 4, 2, 1 길이의 막대 몇 개를 가지고 만들 수 있는지

1. 현재 막대(n)이 x보다 크다면 반으로 나누기
2. 그렇지 않다면 x에서 n 빼주고 갯수 증가

📄 코드

x = int(input())

n = 64
answer = 0

while x > 0:
    if n > x:
        n //= 2
    else:
        x -= n
        answer += 1

print(answer)

• 시간복잡도: O(1)