[백준 1094] 막대기 (C#, C++) - soo:bak

문제 링크

1094번 - 막대기

설명

이 문제는 길이 64인 막대를 절반으로 자르면서, 목표 길이 X를 만드는 최소한의 막대 조각 수를 구하는 문제입니다.

---

접근법

이 문제는 본질적으로 목표값 X를 만들기 위해 어떤 2의 거듭제곱을 조합할 수 있는지를 찾는 문제입니다. 즉, X를 이진수로 표현했을 때 1의 개수가 정답입니다.

구체적인 과정은 다음과 같습니다:

• 초기 상태에서 길이 64인 막대 하나만 있습니다.
• 현재 막대 조각들의 합이 X보다 크다면, 가장 짧은 막대를 절반으로 자릅니다.
• 절반으로 자른 막대 2개 중 하나를 버릴지, 유지할지를 결정합니다:
  • 자른 후 하나만 남기면 총합이 X보다 작아지는 경우, 둘 다 유지해야 합니다.
  • 그렇지 않으면 하나는 버립니다.
• 이 과정을 반복하면서 막대 조각들의 총합이 정확히 X가 되는 시점을 찾습니다.
• 이때 남아있는 막대 조각의 개수가 정답입니다.

직접 위 과정에 따라서 직접 구현을 진행해도 괜찮지만, 답을 가장 빠르게 구현하는 방법 중 하나는 이진수의 비트 단위 처리 입니다.

풀이 과정은 결국 X를 2의 제곱수들의 합으로 분해하는 과정과 같으며,
목표값을 만드는 데 필요한 최소 막대 수는 결국 X를 이진수로 나타냈을 때 1의 개수와 같기 때문입니다.

---

Code

[ C# ]

using System;
using System.Collections.Generic;
using System.Linq;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var target = int.Parse(Console.ReadLine()!);
      var sticks = new List<int> { 64 };

      while (true) {
        var sum = sticks.Sum();
        if (sum == target) {
          Console.WriteLine(sticks.Count);
          break;
        }

        var min = sticks.Min();
        sticks.Remove(min);
        min /= 2;
        if (sum - min < target)
          sticks.Add(min);
        sticks.Add(min);
      }
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tar; cin >> tar;

  int cnt = 0;
  while (tar) {
    cnt += tar & 1;
    tar >>= 1;
  }

  cout << cnt << "\n";

  return 0;
}