💻 백준 1094: 막대기

문제 소개 🧐

길이가 64cm인 막대를 잘라서 Xcm 막대를 만드는 문제. 막대를 절반으로 자르는 과정을 반복하며, 남은 막대들의 길이 합이 X가 되도록 할 때, 최종적으로 사용된 막대의 개수를 구해야 한다.

  • 핵심 규칙:
    1. 처음 막대는 64cm.
    2. 막대들의 합이 X보다 크면, 가장 짧은 막대를 절반으로 자른다.
    3. 자른 막대의 절반 중 하나를 버려도 합이 X 이상이면, 버린다.

입력 📝

  • X (64 이하의 자연수)

출력 📤

  • Xcm를 만드는데 필요한 막대의 개수

제한 ❌

  • 2초, 128MB

첫 번째 시도: 시뮬레이션 👊

Idea

문제에 주어진 과정을 그대로 따라가며 구현했다. 64부터 시작해서 계속 절반으로 나누고, 현재 가진 막대들의 합과 X를 비교하며 막대를 추가하거나 버리는 방식

Code

import sys

x = int(sys.stdin.readline().rstrip())

cnt = 0
cur_len = 64

while x>0:
    if x - cur_len == 0:
        cnt += 1
        x -= cur_len
        print(cnt)
    elif x -cur_len < 0:
        pass
    else:
        x -= cur_len
        cnt += 1

    cur_len = cur_len >> 1

Result

  • 성공! ✅

두 번째 시도: 비트마스킹 ✨

Idea

문제의 막대 길이(64, 32, 16, …)가 2의 거듭제곱 형태인 것을 보고, X를 2진수로 변환했을 때 1의 개수가 곧 필요한 막대의 개수와 같다는 것을 깨달았다.

Code

import sys
from collections import Counter

x = int(sys.stdin.readline().rstrip())

print(Counter(bin(x)).get('1'))

Result

  • 성공! ✅

개선할 부분 🤔

  • 2진수와 관련된 문제에서는 비트마스킹을 활용하면 훨씬 간결하고 효율적인 코드를 작성할 수 있다는 점을 기억해야겠다.