막대기- 백준 1094

풀이

x = int(input())
sticks = [64]
remain = 0
while True:
    remain = sum(sticks)
    if remain == x:
        break
    tmp = sticks.pop() // 2
    sticks.append(tmp)
    if sum(sticks) < x:
        sticks.append(tmp)

print(len(sticks))

자료구조인 스택의 속성을 이용했다. 가장 짧은 막대기가 sticks의 맨 끝에 들어가기 때문에 sticks.pop()으로 꺼낼 수 있다.

1-2 조건을 역으로 생각하면, 가장 짧은 막대의 절반을 제외한 나머지의 합이 원하는 사이즈보다 작을 때 제외했던 절반을 다시 넣어 합하면 된다.