백준 1094 : 막대기

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

1094번: 막대기

 

#include <iostream>
 
bool binaryArr[8];
int X, ans;
 
void input()
{
    std::cin >> X;
}
 
void solve(int stk, int up, int down)
{
    int mid = up + (down - up) / 2;
    if (mid == X || down == X)
    {
        ans = stk;
        return;
    }
    else if (mid < X)
    {
        solve(stk + 1, mid + 1, down);
    }
    else if (mid > X)
    {
        solve(stk + 1, up, mid - 1);
    }
}
 
void binary_solve()
{
    int i = 1;
    while (X != 0)
    {
        binaryArr[i++] = X % 2;
        X /= 2;
    }
    for (int i = 1; i < 8; ++i)
    {
        if (binaryArr[i])
        {
            ++ans;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    //solve(1, 1, 64);
    binary_solve();
    output();
    return 0;
}

 

첨엔 이분탐색 아녀?? 했다가

 

아차차

 

33같은 경우엔 32cm 막대 하나랑 1cm 막대 하나가 필요하다

 

헌데 막대를 자르는 기준은 절반으로 나누는 것이고

 

최대 막대 길이는 64이다

 

64 32 16 8 4 2 1

 

아하!