1094번: 막대기

문제

지민이는 길이가 64cm인 막대를 하나 가지고 있습니다. 지민이는 이 막대를 이용해 Xcm 크기의 막대를 만들려고 합니다. 막대를 자르는 과정은 다음과 같습니다.

1. 지민이가 가지고 있는 막대의 길이를 모두 더합니다. 처음에는 64cm 막대 하나만 가지고 있습니다.
2. 가지고 있는 막대의 길이 합이 X보다 크다면, 아래 과정을 반복합니다.
   • 가지고 있는 막대 중 가장 짧은 것을 절반으로 자릅니다.
   • 만약, 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이 합이 X보다 크거나 같다면, 그 절반을 버립니다.
   • 그렇지 않다면 버리지 않고 모두 보관합니다.
3. 위 과정을 거친 후 남은 막대들을 풀로 붙여서 Xcm를 만듭니다.

목표 길이 X가 주어질 때, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 문제입니다.

• 입력: 첫째 줄에 X가 주어집니다. (1 ≤ X ≤ 64, X는 자연수)
• 출력: 문제의 과정을 거친 후 남은 막대의 개수를 출력합니다.

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

풀이 1: 우선순위 큐를 활용한 시뮬레이션

가장 짧은 막대를 반복적으로 찾아야 하므로, 최솟값을 항상 루트에 보장하는 **우선순위 큐(Priority Queue)**를 사용한 정석적인 시뮬레이션 방법입니다.

1. 초기화: 목표 합계(sum)를 64로, 우선순위 큐(pq)에 64를 하나 넣고 시작합니다.
2. 반복 및 조건 분기 (sum > x): 막대들의 총합이 X보다 클 때까지 반복합니다.
   • 큐에서 가장 짧은 막대(shortest)를 꺼내 절반(shortest / 2)으로 자릅니다.
   • sum - shortest / 2 >= x: 절반을 버려도 합계가 X 이상이라면, 절반을 과감히 버리고 총합(sum)에서도 뺍니다.
   • else: 절반을 버렸을 때 X보다 작아진다면, 자른 절반을 버릴 수 없으므로 큐에 다시 보관(pq.add(shortest / 2))합니다.
3. 나머지 절반 보관: 위 조건과 관계없이 막대를 잘랐다면 무조건 절반 하나는 큐에 가지고 있어야 하므로 루프 마지막에 pq.add(shortest / 2)를 수행합니다.
4. 결과 출력: 반복이 끝난 후, 큐에 남아있는 원소의 개수(pq.size())가 바로 정답이 됩니다.

코드 1: 시뮬레이션

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int x = Integer.parseInt(br.readLine());

       int sum = 64;
       PriorityQueue<Integer> pq = new PriorityQueue<>();
       pq.add(64);

       while (sum > x) {
          int shortest = pq.poll(); // 가장 짧은 막대를 꺼냄
          
          // 절반을 버려도 X 이상이라면 버림 처리
          if (sum - shortest / 2 >= x) {
             sum -= shortest / 2;
          } 
          // 버릴 수 없다면 절반을 큐에 보관
          else {
             pq.add(shortest / 2);
          }
          
          // 공통적으로 남은 절반은 큐에 보관
          pq.add(shortest / 2);
       }

       // 큐에 남은 막대의 개수 출력
       bw.write(pq.size() + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

풀이 2: 비트마스킹

막대의 길이가 64, 32, 16, 8, 4, 2, 1과 같이 정확히 2의 거듭제곱 형태로만 잘립니다. 이러한 막대들을 합쳐서 X를 만든다는 것은 결국 X를 이진수로 나타냈을 때 1인 비트의 개수를 구하는 것과 완전히 똑같습니다.

예를 들어 X가 23이라면, 이진수로는 10111(2)가 되며 이는 16 + 4 + 2 + 1 = 23과 같습니다. 이때 필요한 막대는 16, 4, 2, 1 짜리 총 4개입니다. 자바의 Integer.bitCount() 메서드를 사용하면 이 로직을 단 한 줄로 줄일 수 있습니다.

코드 2: 비트마스킹

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int x = Integer.parseInt(br.readLine());

       // 정수 x를 이진수로 변환했을 때 1의 개수를 반환
       bw.write(Integer.bitCount(x) + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

수학, 비트마스킹 (Bitmasking), 시뮬레이션, 우선순위 큐 (Priority Queue)