[백준/Python] 1094 - 막대기

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

구현 과정

입력받은 x가 64면 그냥 1을 출력하고 종료하면 된다.
아닌 경우에 대해서는, 자른 막대기들의 길이 합 sum(sticks)가 x가 아닌 동안 자르고 비교하고 막대기를 추가하는 과정을 반복해야 한다.

1. minStick = min(sticks) 현재 막대기들 중 가장 작은 막대기 찾기
2. half = minStick // 2 가장 작은 막대기를 절반으로 자른 막대기의 길이 구하기
3. 막대를 절반으로 자르면 총 두 개의 조각이 새로 생긴다. 이 두 조각을 모두 유지할지, 하나만 버릴지를 골라야 한다.
   1) sticks.remove(minStick) 절반으로 잘랐으므로, 원래 제일 작았던 막대기는 이제 없는 것이다. 리스트에서 제거해준다.
   2) sticks.append(half) 절반 조각이 생긴 것이므로 이를 추가해준다.
4. 막대기들의 길이 합이 x보다 같거나 큰 경우에는 계속해서 막대기 길이를 줄여야 하므로 continue 한다. 막대기들의 길이 합이 x보다 작은 경우에는 아까 잘라낸 막대기의 절반 조각을 다시 리스트에 append 해준다. 아까 절반으로 쪼갠 일을 없던 일 취급하는 것과 같다!

필요한 막대기의 총 개수는 len(sticks)로 구할 수 있다. 이를 출력하고 종료한다.

전체 코드

x = int(input())

stick = 64
sticks = [stick]

if x == 64:
    print(1)
else:
    while sum(sticks) != x:
        minStick = min(sticks)
        half = minStick // 2

        sticks.remove(minStick)
        sticks.append(half)

        if sum(sticks) >= x:
            continue
        else:
            sticks.append(half)

    print(len(sticks))