[백준 1094] 막대기

0. 제목

• 백준 1094 막대기
• BOJ 1094 막대기
• C++ 1094 막대기

---

1. 문제

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

---

2. 풀이

• 처음에 길이가 64인 막대기를 가지고 있다.
• 현재 막대기가 만들고자 하는 막대기보다 길면 가지고 있는 막대기를 반 자른다.
• 짧다면 만들고자 하는 막대기에서 현재 막대기 길이를 뺀 후 갱신기킨다. 또한 막대기 한 개를 사용했으므로 cnt값을 1 증가시켜준다.
• X가 0이 되면 루프가 종료되고 cnt값이 필요한 막대기의 수가 된다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int X;
    int len = 64;
    int cnt = 0;
    
    cin >> X;
    while(X > 0){
        if(len > X)
            len = len / 2;
        else{
            X -= len;
            cnt++;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}