https://www.acmicpc.net/problem/1094
1094번: 막대기
지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대
www.acmicpc.net
🔔 문제 :
64cm 막대기 하나를 반씩 잘라서 나오는 막대기들을 가지고 1 <= X <= 64인 자연수 X를 만들려면 막대기 몇개가 필요한지를 구하는 문제입니다.
즉 2^0 , 2^1, 2^2, 2^3, 2^4, 2^5, 2^6인 1, 2, 4, 8, 16, 32, 64cm 막대기를 사용할 수 있습니다.
예를들어 X = 23인경우, 16 + 4 + 2 + 1 로 정답은 4개가 됩니다.
🔔 Kick Point :
X보다 차이가 가장 적은 막대기를 지속적으로 빼다가 X가 0일때 막대기의 수를 출력해주었습니다.
🔔 Code :
#include <iostream>
using namespace std;
int main() {
int X;
cin >> X;
int stick = 64;
int cnt = 0;
while (X) {
if (stick > X) stick /= 2;
else {
X -= stick;
++cnt;
stick = 64;
}
}
cout << cnt;
}