[백준/C++] 1094 막대기

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

1094번: 막대기

처음 64cm 라는 길이의 막대기를 가지고

원하는 xcm 의 막대기를 만들기위해 처음가진 막대기르 반으로 나누고

나누었을때 x크기보다 크면 다시나누고 작으면 나눈 다른한쪽을 나눠 붙여 가며 x의 수를 만드는 데 몇번 붙였는지를 구하는 문제.

 

나중에 찾아보니 이진법의 규칙을 활용한 문제라고한다..

 

풀이

// 백준 막대기 문제 풀이
#include <iostream>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

int main()
{
	fastio;
    int x;
    cin >> x;
    int length = 64, sum = 0, count = 0;
    while (sum != x)  // 합친막대와 원하는길이X 가같지않다면반복
    {
        if (length + sum > x) // 원하는길이보다 크다면 길이를나눠주고
        {
            length /= 2;
        }
        else // 원하는길이보다작다면 합계에더하고 다시길이를 반으로쪼갠다
        {
            sum += length;
            length /= 2;
            count++; // 붙이는 카운트 증가
        }
    }
    cout << count;
    return 0;
}