[파이썬, Python] 백준 1094: 막대기

문제

https://www.acmicpc.net/problem/1094

1094번: 막대기

코드

x = int(input())
sticks = [64]


while True:
    if sum(sticks) > x:
        stick = min(sticks) // 2
        sticks.remove(min(sticks))
        
        if stick + sum(sticks) >= x:
            sticks.append(stick)
        else:
            sticks.append(stick)
            sticks.append(stick)
            
    elif sum(sticks) == x:
        break
        
print(len(sticks))

x = int(input())
cnt = 0

while x != 0:
    if x % 2 == 1:
        cnt += 1
    x = x // 2

print(cnt)

설명

문제 설명을 진짜 못했다고 생각했던 문제였다.

설명을 이해하는데 애를 먹어서 처음에 단순 구현으로 풀이를 했고,
풀다 보니 이렇게 어렵게 풀 이유가 없는 문제라고 생각해서 잠깐 검색해 본 결과로 나온 게 2번째 풀이였다.

1번 풀이의 경우 문제의 요구사항을 그대로 구현한 것인데

1. 우선 가지고 있는 막대의 가장 짧은 막대를 절반으로 자른다.
2-1. 자른 길이가 목표 길이보다 길다면 하나를 버린다.
2-2. 자른 길이가 목표 길이보다 짧다면 둘 다 사용한다.
3. 반복해서 목표 길이를 만든다.
4. 목표 길이에 도달하면 반복문을 종료하고 막대의 개수를 출력한다.

이러한 요구사항이었는데 2번이 굉장히 불친절하게 설명 되어있다.
그래도 이해만 한다면 금방 풀이가 가능했다.

2번 풀이의 경우 수학적 성질을 이용한 풀이인데,
이진법으로 변환했을 때 1의 개수를 세면 된다고 한다.

문제의 23의 경우 이진법으로 변환하면 10111이 되므로 답이 4라는 것이다.