[ 백준 1094 ] 막대기 (C++)

백준의 막대기(1094) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 64cm의 막대로 입력으로 주어지는 원하는 X cm의 막대를 만들어야 하는 문제이다.

- 문제의 조건에 맞게 막대기를 반으로 나눌 수 있으며, 버릴 수 있다.

- 남아있는 막대기를 다 더해서 X cm의 막대를 만들어야 한다.

< 문제의 조건 >

[ 문제풀이 ]

1. 문제의 조건이 이해가 잘 안될수도 있다.(내가 처음에 그랬다) 조건을 쉽게 요약해보자면 64cm의 막대기를 계속해서

   반으로 쪼갤수가 있는데, 이 때, 만들고자 하는 막대길이인 X cm를 기준으로, Xcm보다 크면 자른 막대들 중 하나를 버리고

   Xcm보다 작다면 그 작은 막대를 사용하고, 남은 다른 한쪽의 막대를 또 반으로 쪼개서 X cm를 만들라는 것이다.

2. 풀이과정은 생각보다 간단하다. 내가 가지고 있는 현재길이(사용한 변수 : Len) 가 X보다 크다면

   막대를 쪼개면 된다. Len = Len/2

   X보다 작다면, 그 막대를 사용하고, 나머지 막대를 이용해서 남은 부분을 채우면 된다.

   즉, X = X - Len이 되고, 다시한번 Len = Len/2 를 하는 과정을 반복하면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int X;
 
void Input()
{
    cin >> X;
}
 
void Solution()
{
    int Len = 64;
    int Cnt = 0;
    while (X > 0)
    {
        if (Len > X) Len = Len / 2;
        else
        {
            X = X - Len;
            Cnt++;
        }
    }
    cout << Cnt << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}