백준 | 막대기

백준 막대기

스택을 사용해 문제의 조건을 그대로 구현하면 된다.

# 정답

import sys

# 입력
x = int(sys.stdin.readline().strip())

# Xcm를 만들 수 있는 막대의 개수 구하기
sticks = [64]
while sum(sticks) != x:
    shortest_stick = sticks[-1]

    if sum(sticks) - (shortest_stick // 2) >= x:
        sticks.pop()
        sticks.append(shortest_stick // 2)
    else:
        sticks.pop()
        sticks.append(shortest_stick // 2)
        sticks.append(shortest_stick // 2)

# 출력
print(len(sticks))

다르게 생각하면.. x를 2진수로 표현했을 때의 1의 개수가 x cm를 만들기 위한 막대기의 개수이다.

따라서 다음과 같은 코드도 가능하다!

# 정답

import sys

x = int(sys.stdin.readline().strip())
print(bin(x).count('1'))