[BOJ] 백준 1094 막대기

출처: https://www.acmicpc.net/problem/1094

Approach

문제에서는 아래와 같이 정의하였다.

1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고
   남아있는 막대의 길이의 합이 X보다 크거나 같다면,
   위에서 자른 막대의 절반 중 하나를 버린다.
   이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

64 길이의 막대기가 주어지고

가장 짧은 막대의 길이는 점차 반으로 줄어들어 나갈 때,

32 → 16 → 8 → 4 → ...

해당 조합(?)으로 목표 길이를 구성하는 것이다.

 

23 = 16 + 4 + 2 + 1 인데, 아래와 같이 계산할 도 있다.

#include <stdio.h>

int X, ans, len = 64;
int main(void)
{
	// freopen("input.txt", "r", stdin);
	scanf("%d", &X);
	while (X > 0)
	{
		if (len > X)
		{
			len = len / 2;
		}
		else
		{
			X = X - len;
			ans++;
		}
	}
	printf("%d\n", ans);
}

 

결과적으로 해당 문제는 X를 2진수로 표현했을 때,

1 bit 개수를 찾는 것이다.

 

23 → "10111" → 1bit 개수 = 4개

절반으로 자른다는 것에서 >> (Shift)연산으로 처리할 수 있다.　

#include <stdio.h>

int X, ans;
int main(void)
{
	// freopen("input.txt", "r", stdin);
	scanf("%d", &X);
	for (; X; X >>= 1)
		ans += X & 1;
	
	printf("%d\n", ans);
}