[백준] 1094 막대기 with C++

문제설명

---

입출력 예제

---

개념

　이 문제는 64cm 막대기를 이용하여 길이가 Xcm인 막대기를 만드는 문제다. 이때, 우리가 사용할 수 있는 도구는 막대기를 정확히 절반으로 자르는 것뿐이다. 따라서, 가능한 막대기의 길이는 64, 32, 16, 8, 4, 2, 1cm 등 2의 거듭제곱 형태다. 이는 우리가 풀려고 하는 문제를 이진수 표현으로 해석하는 키가 된다.

　각 이진수의 자리는 2의 거듭제곱을 나타내며, 우리가 필요한 막대의 개수는 이진수 표현에서 1의 개수와 같다. 이는 막대기를 사용하느냐, 사용하지 않느냐를 이진수의 1과 0으로 표현한 것과 같다. 이런 점에서 볼 때, 이 문제는 그리디 알고리즘을 사용하여도 풀 수 있다.

　그리디 알고리즘을 사용하는 경우, 가장 큰 막대부터 시작하여 목표 길이를 초과하지 않는 한 계속 막대를 추가한다. 이렇게 하면 목표 길이를 만족시키는 데 필요한 막대의 최소 개수를 구할 수 있다. 이 과정은 스택 자료구조를 사용하면 효율적으로 구현할 수 있다.

---

풀이(1) 이진법

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
	int X;
	cin >> X;

	bitset<32> binary_X(X);
	int cnt = 0;

	for (int i = 0; i < binary_X.size(); ++i)
	{
		if (binary_X[i] == 1)
			cnt++;
	}

	cout << cnt;
}

　주어진 수를 이진수로 변환한 뒤, 1의 개수를 찾으면 된다. 왜냐하면 결국 1은 해당 자리의 값을 사용함을 의미하고, 0은 해당 자리의 값을 사용하지 않음을 의미하기 때문이다. 가령 X = 23인 경우, 이를 이진수로 나타내면 10111(2)이므로, 1cm, 2cm, 4cm, 16cm 막대기가 필요하다는 것이다.

 

풀이(2) 그리디 알고리즘

#include <iostream>
#include <cmath>
#include <stack>
using namespace std;

int main()
{
	int X, sum = 0, cnt = 0;
	cin >> X;

	stack<int> st;

	for (int i = 0; i <= 6; ++i)
		st.push(pow(2, i));

	while (true)
	{
		if (sum + st.top() <= X)
		{
			sum += st.top();
			st.pop();
			cnt++;
		}

		else
			st.pop();

		if (sum == X)
		{
			cout << cnt;
			break;
		}
	}
}

　위의 과정을 스택을 이용해 가장 큰 수부터 하나씩 더해가며 합이 X가 되는지 검사하도록 구현하였다.