[1094] 막대기

---

문제 설명이 너무 이상해서 검색을 해보았다.

64cm의 막대기를 계속 절반으로 쪼개면서 Xcm의 막대기로 만드는 것이다.

 

 

예를 들면 23cm의 막대기를 만들고 싶으면

23cm = 16cm + 4cm + 2cm + 1cm : 총 4개의 막대기 필요

 

48cm의 막대기를 만들고 싶으면

48cm = 32cm + 16cm : 총 2개의 막대기 필요

 

 

64cm부터 시작해서 계속 절반으로 쪼갰을 때,

Xcm보다 작아진다면 X로부터 만들어진 막대기의 길이를 빼주기(X=X-cur)를 반복하다가

X가 0이 되면 종료하고 막대기의 개수를 출력한다.

 

전체 코드는 아래와 같다.

#include <iostream>
using namespace std;

int X;
// 64 32 16 8 4 2 1
// 23 = 16 + 4 + 2 + 1 => 4개
// 48 : 32 + 16 => 2개
int cnt;

int main(){
	cin >> X;

	int cur = 64; // 64부터 쪼개기 시작
	while (1) {		
		if (cur > X) { // 원하는 수보다 아직 크면
			cur /= 2; // 반절로 쪼개기
		}
		else {
			if (X - cur >= 0) { // cur(cm)의 막대기로 X를 구성할 수 있다면
				X = X - cur; // cur(cm) 빼주고
				cnt++; // 횟수 증가
			}
		}
		if (X == 0) break; // 구성이 완료됐으면 while문 탈출
	}
	cout << cnt; // 횟수 출력
}