[C++] 백준 1094번 : 막대기

#include <iostream>
#include <string>
#include <bitset>
#define N 8
using namespace std;


int main()
{
	int x = 0;
	cin >> x;

	string binary = bitset<N>(x).to_string();

	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (binary[i] == '1')
		{
			count++;
		}
	}
	cout << count << endl;

	return 0;
}

문제

 

문제코드

#include <iostream>
#include <string>
#include <bitset>
#define N 8
using namespace std;


int main()
{
	int x = 0;
	cin >> x;

	string binary = bitset<N>(x).to_string();

	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (binary[i] == '1')
		{
			count++;
		}
	}
	cout << count << endl;

	return 0;
}

 

문제풀이

해당 문제는 Bitset을 알아야 풀 수 있는 문제입니다. 

먼저 처음에 64cm를 가지고 있고 이후 계속 절반으로 나눕니다. 절반만 사용하므로 사용할 수 있는 막대기의 길이는 

- 1, 2, 4, 8, 16, 32, 64에 해당합니다.

 

그렇다면 이는 2진수로 생각을 할 수 있습니다. 내가 만들 수 X에 대해 이진수로 변환한 후에 1의 개수를 구하면 그 값이 X의 막대기의 개수가 되는 것입니다.

 

ex)  64 : 0100 0000 이므로 1개
       15 : 0000 1111 이므로 4개

따라서 해당 문제는 x를 이진수로 변환해 1의 개수를 출력하면 되는 간단한 문제입니다. 하지만 bitset을 모른다면 2진수를 출력할 수 없기 때문에 해당 문제에서 박힌 분들은 bitset에 대한 개념이 부족해서 그런 것입니다.

 

물론 해당 문제 풀이로 말고 vector로 따라가면서 풀어도 풀 수 있습니다.

 

bitset 란?

 

bitset는 c++ 표준 라이브러리에서 제공하는 템플릿 클래스로 고정 크기의 비트를 관리하고 각 비트에 대해서 개별적인 조작을 할 수 있는 것입니다. 

 

bitset<8>은 8개의 비트를 가지는 bitset의 객체를 의미합니다. 

	string binary = bitset<N>(x).to_string();​

여기서 N은 #define 8로 되어 있기 때문에 8에 해당합니다. 즉 8비트의 비트셋을 생성하는 것입니다. bitest<8>(x) 는 정수 x를 8비트의 이진수로 변환합니다. 예를들면 x가 5이면 이진수로 '0000 0101' 이 생성되는 것입니다. 

 

이 생성된 객체을 판별하려면 문자열로 받아들여서 하나하나씩 분석해서 찾아줘야 하는데요. 따라서 to_string을 통해 비트셋을 문자열로 변환합니다. 

 

다른 풀이

#include <iostream>
#include <string>
#include <vector>
using namespace std;


int main()
{
	int x, i, total;
	vector<int> v;

	v.push_back(64);
	total = v[0];

	cin >> x;
	i = 0;

	while (1)
	{
		if (total == x)
		{
			break;
		}

		v[i] /= 2;

		if (total - v[i] >= x)
		{
			total -= v[i];
		}
		else
		{
			v.push_back(v[i]);
			i++;
		}
	}

	cout << v.size() << endl;

	
	return 0;
}

bitset을 사용하지 않고 푼 것입니다. vector의 길이를 추가하면서 vector가 count의 역할을 해주는 것입니다. 그리고 v[i]는 각각의 막대기의 길이에 해당하며 total은 막대기의 버리는 수에 해당합니다.

 

문제를 계속해서 따라서 코딩을 하면 이런 식으로 할 수 있습니다.

 

원래의 의도에 맞춰 본다면 첫 번째 풀이가 정석이라고 볼 수 있습니다.