-> 위에서 자른 막대의 절반을 바로 버리는 것이 아님, 제외하고라는 표현이 어울림.
: 질문 게시판에도 수정요청 있음.
1) 벡터 컨테이너에 64를 집어 넣고 시작
2) back에 있는 것을 뽑아서 반절로 만듬.
3) 벡터의 모든 원소를 더한 다음에 2번에서 구한거랑 뺌
4) n과 비교를 해서
5 - 1) 작다면 back에 있는거를 반절로 만들고, 2번의 막대기를 추가함.
5 - 2) 크다면? back에 있는거를 반절로 만듬.
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
// 23:14 ~ 23:43
int main()
{
//64 -> 23으로 만들어야 함.
//횟수를 구하라.
// 64
// vs 48
// 64 -> 32 32
// 32 16 16 -> 16제외하고 32 + 16 더함 -> 48 총 2개의 막대.
//64
// vs23
// 32 32 -> 32버림 카운트 1
// 16 16 -> 16하나 제외하고 16 vs 23 작으므로 안버림 , 카운트 2
// 16 8 8 -> 8하나 제외하고 , 24 vs 23 크므로 8버림, 카운트 3
// 16 4 4 -> 4하나 제외하고 20 vs 23 작으므로 안버림.,
// 16 4 2 2 -> 2하나 제외하고, 22 vs 23 작으므로 안버림.
// 16 4 2 1 1 -> 1하나 제외하고, 23 vs 23 동일하므로 1을 버림.
// => 남은 막대는 총 16 4 2 1 //4개임.
int n;
cin >> n;
vector<int>v(1, 64);
int stick = 64;
int cnt = 1;
if (n == 64)
{
cout << v.size() << endl;
return 0;
}
while (1)
{
// 길이가 가장 짧은 것을 반으로 자름.
int half = v.back() / 2;
int temp = 0;
for (int i = 0; i < v.size(); ++i)
{
temp += v[i];
}
temp -= half;
if (temp >= n)
{
//마지막 인덱스의 원소를 반절로 해야 함.
v[v.size() - 1] -= half;
}
//오히려 막대기 추가함.
else
{
v[v.size() - 1] -= half;
v.push_back(half);
}
if (temp == n)
{
cout << v.size() << endl;
return 0;
}
//남아 있는 막대기의 합이
}
}