백준 1094번: 막대기

백준 온라인 저지(BOJ) 1094번 문제

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

1. 문제 요약

64cm의 막대기를 가지고 Xcm의 막대기를 만들기.

이 때 다음의 방법을 이용한다.

1. 가지고 있는 막대의 길이를 모두 더해서 X보다 크면, 그 중 가장 작은 길이의 막대기를 절반으로 자른다.

2. 자르고 그 중 하나를 버렸을 때 그 합이 X보다 크거나 같으면 하나를 버린다.

위 과정을 반복해, 남아있는 막대의 합이 X가 되도록 만든다.

이 때 위 과정을 거친다면 몇 개의 막대를 풀로 붙여야 Xcm를 만들 수 있을까?

2. 알고리즘

뭔가 표현은 복잡하지만, 분석해보면 간단함을 깨달을 수 있을 것이다.

64cm부터 시작해서, 가장 짧은 막대의 길이는 점차 반으로 줄어들어 32, 16, 8, 4, ...cm가 될 것이고

이 때 이들의 합으로 목표로 한 막대의 길이를 만들어야 한다.

즉, 이 문제는 주어진 숫자 X를 이진법으로 나타냈을 때 각 자리수 중 1이 몇 개 있는지 묻는 문제와 동치인 것이다.

3. 코드

#include <iostream>
using namespace std;

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

	int r = 0;
	while (X != 0) {
		if (X % 2 == 1) r++;
		X /= 2;
	}
	cout << r << '\n';

}

190720 내용추가) __builtin_popcount()를 이용하면 편하다