[백준]1094막대기 C++

비트마스킹 문제이다.

#include<iostream>

using namespace std;



int main()
{
	
	int temp = 0;
	for (int i = 0; i < 10; i++)
	{
		
		temp = (1 << i);
		cout << temp << endl;
	}
	


}

이 코드를 돌려보면 

이렇게 나온다. 

temp  -> 1     2^0=1

temp  ->10    2^1=2

temp -> 100  2^2=4 

temp -> 1000 2^3 =8

temp -> 10000 2^4 =16

.

.

temp ->1000000  2^6 =64

#include<iostream>

using namespace std;

//지민이가 가지고 있는 막대의 길이를 모두 더한다.처음에는 64cm 막대 하나만 가지고 있다.이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
//가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
//만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
//이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int x;
	cin >> x;
	int stick = 64;
	int half = 64;
	while (true)
	{
		if (stick != x)
		{
			half = half >> 1;
			//만약, 위에서 자른 막대의 절반 중 하나를 버리고 
			//남아있는 막대의 길이의 합이 X보다 크거나 같다면
			if (stick-half >= x)
			{
				stick -= half; //이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다
			}
			
		}
		else
		{
			break;
		}
		
		
	}
	int count = 0;
	for (int i = 0; i < 7; i++)
	{
		if (stick&(1 << i))
			count++;
	}
	cout << count;
	
	
}

이렇게 풀어서 맞았는데 비트마스킹을 잘 활용 못한 것 같아서 다른 사람의 풀이를 찾아봤다

x의 비트를 세주는 방법으로 하면 몇 번 잘랐는지 알게 된다고 한다.

마지막 비트를 꺼주는 방법은 자기보다 1작은 수와 & 연산을 하면 된다고 한다.

ex) x= 10 ,  x-1=9

1010 & 1001 ->1000

이런식으로 x가 0이 될때까지 마지막 비트를 꺼주면서 count 해주면 된다.

또다른 방법은

1을 왼쪽으로 한칸씩 쉬프트하면서 X와 & 연산을 하는 것이다. 

x &(1<<i)     x의 i 번 째 비트가 1이면 저 식이 참이 되기 때문에 그럴 때마다 count해주면된다.

(0<=i<=6)

 

느낀점

문제를 그대로 직역해서 막대기를 자라는 것에 집중했는데

x를 보고 얼마나 잘랐는지 세어주는 방법으로도 할 수 있다는 것이 신기했다.

문제를 그대로 코드로 바로 옮기지 말고  거꾸로도 생각해봐야겠다.