막대기

분석

쪼개고 쪼개고 쪼개었을 때 합이 x가 되는지를 확인

후기

좀 쉬운 느낌이 들었지만 중간에 문제뜻을 확인하는데 조금 햇갈렸음.

"합이 x보다 크다면 가지고있는 막대중 길이기 가장 짧은 것을 절반으로 자른다"

이부분에서 막대가 하나일 경우 뭐가 가장 짧은건지 말이 이해가 안갔었는데 예제를 보니까 막대기가 하나일 경우 그녀석을 자르면되었었다.

cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long

int x, origin = 64, cnt = 1;
vector<int> vec;

int Sum()
{
	int sum = 0;
	for (int v : vec) sum += v;
	return sum;
}

void CutHalf()
{
	int v = vec.back();
	vec.pop_back();
	vec.push_back(v / 2);
	vec.push_back(v / 2);
}

bool Check()
{
	int sum = 0;
	int left = vec.back();
	for (int v : vec) sum += v;
	sum -= left;
	if (sum >= x) return true;
	else return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> x;
	vec.push_back(64);
	while (1)
	{
		if (Sum() > x)
		{
			CutHalf();
			if (Check()) vec.pop_back();
		}
		else
		{
			if (Sum() == x) break;
		}
	}

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

	return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
int n;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int ret = 1;
	while (n != 1)
	{
		if (n & 1) ++ret;
		
		n /= 2;
	}
	cout << ret << endl;

	return 0;
}