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

 

문제 URL:

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

1094번: 막대기

 

이 문제는 원래 가지고 있던 64cm의 막대를 더 작은 막대로 자른 다음, 풀로 붙여서 길이가 Xcm인 막대를 만들 때 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 문제이다.

 

문제를 보면 X가 가지고 있는 막대 중 길이가 가장 짧은 것(=length)보다 작거나 같을 때

Xcm를 만드는데 필요한 막대를 찾은 것이다. 

따라서 위 조건일 때, ans를 1 증가시키고 X에서 length를 빼주는 방식으로 문제를 해결하였다. 

---

#include <iostream>
using namespace std;

int x;
int ans = 0;
int length = 64;

int main() {
	cin >> x;

	while (x > 0) {
		if (length > x)  // 조건 1-1
			length /= 2;
		else {  // Xcm를 만드는데 필요한 막대를 찾음
			ans++;
			x -= length;
		}
	}
	cout << ans;
}