[백준/파이썬] 1094번 막대기 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1094번 막대기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

길이 64 막대기를 잘라서 길이 합이 x가 되도록 만들 때, 필요한 막대기 개수를 구하는 문제입니다.

코드

x = int(input())

sticks = [64]

while sum(sticks) > x:
    sticks.sort(reverse=True)
    sticks[-1] //= 2
    if sum(sticks) >= x:
        continue
    sticks.append(sticks[-1])
print(len(sticks))

설명

가장 짧은 막대기를 반으로 자르고, 잘라낸 뒤 합이 x 이상이면 한 조각을 버립니다. 합이 x보다 작아지면 버리지 않고 두 조각 모두 유지합니다.

이 과정을 반복하면 최종 막대기 개수가 답입니다.

---

• 백준 문제풀이 전체 목록 보기

---