백준 1094번 막대기 Python

백준 1094번 막대기 (Python)

문제

● 문제 설명

한 사람이 길이 64cm인 막대를 가지고 있습니다.

그는 이 막대를 자르기 시작합니다.

자를 때는 항상 절반으로만 자를 수 있습니다.

자른 막대 중 일부를 버리거나 남길 수 있습니다.

남은 막대의 총합이 원하는 길이 N과 같아지면 그만 자릅니다.

즉,

• 64cm 막대 하나를 시작으로,
• 절반으로 나누고,
• 일부를 버리거나 남기면서
• 남은 막대들의 길이 합이 N이 되도록 하는 문제입니다.

● 입력

23

● 출력

4

문제 작동원리

이 문제는 물리적으로 생각하면 막대를 절반씩 나누어가며 길이의 합을 조절하는 원리입니다.

즉, 처음 막대의 길이(64cm)를 기준으로 절반씩 줄여가며

필요한 길이만큼의 합을 남겨두는 과정입니다.

이 원리는 “이진 분할(binary division)”의 구조를 가집니다.

즉,

64 → 32 → 16 → 8 → 4 → 2 → 1

이렇게 계속 절반으로 나누어가며,

각 조각이 남거나 버려지는 형태를 통해

최종적으로 원하는 길이를 표현할 수 있습니다.

이것은 2진수 표현과 같은 원리로 작동합니다.

예를 들어 23을 2진수로 바꾸면 \( 10111 \)이 되는데,

이는 16 + 4 + 2 + 1의 합으로 구성됩니다.

즉, 2의 거듭제곱 단위로 이루어진 조각을 더해서 목표 길이를 만드는 원리입니다.

아이디어

이 코드는 직접적인 시뮬레이션 방식을 사용합니다.

즉, 실제로 막대를 자르고, 더하고, 비교하면서

필요한 조각의 개수를 구합니다.

이 과정은 다음과 같습니다.

과정	막대 상태	설명
시작	[64]	64cm 한 개로 시작합니다.
1	[32, 32]	절반으로 잘라 32cm 두 개를 만듭니다.
2	[32, 16, 16]	32cm 하나를 다시 잘라 16cm 두 개를 만듭니다.
3	[32, 16, 8, 8]	16cm 중 하나를 다시 잘라 8cm 두 개를 만듭니다.
4	[16, 4, 2, 1]	남은 조각 중 일부를 선택하여 23을 만듭니다. (16 + 4 + 2 + 1 = 23)

이 과정을 코드에서는 다음과 같이 표현합니다.

k는 현재 막대의 길이(초기값 64)

temp는 지금까지 더한 길이

cnt는 남긴 막대의 개수

실행 흐름은 다음과 같습니다.

1. k + temp > N이면 현재 조각은 너무 큽니다 → k //= 2
2. k + temp <= N이면 현재 조각을 남깁니다 → temp += k, cnt += 1
3. temp == N이면 종료 후 cnt 출력

즉,

“현재 길이에 이 조각을 더해도 목표를 넘지 않으면 더한다”

는 단순한 비교 구조입니다.

전체 코드

N = int(input())
temp = 0
k = 64
cnt = 0

while True:
    if temp == N:
        print(cnt)
        break
    if k + temp > N:
        k //= 2
    else:
        temp += k
        k //= 2
        cnt += 1

결론

구분	내용
문제 핵심	64cm 막대를 절반씩 나누며 원하는 총 길이 N을 만드는 원리입니다.
작동 원리	절반씩 분할하는 이진 분할(binary division) 구조를 이용합니다.
코드 아이디어	막대를 절반씩 줄여가며 합이 N을 넘지 않으면 더하는 방식입니다.
입력 예시	23
출력 예시	4
결과 해석	16 + 4 + 2 + 1 = 23이므로 막대 4개가 필요합니다.