[#126][알고리즘][백준] 1094. 막대기
[백준] 1094. 막대기
문제 링크(https://www.acmicpc.net/problem/1094)문제
지민이는 길이가 64cm인 막대를 가지고 있다. 어느날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만드려고 한다.
막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.
- 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이 때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
- 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
- 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
- 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.
X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.
출력
문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.
예제 입력 1
23
예제 출력 1
4
예제 입력 2
32
예제 출력 2
1
예제 입력 3
64
예제 출력 3
1
예제 입력 4
48
예제 출력 4
2
#include <iostream>
using namespace std;
int main() {
int input, count=0, left;
cin >> input;
while (input > 0) {
left = input % 2;
if (left == 1) {
count++;
}
input /= 2;
}
cout << count << endl;
return 0;
}
| cs |
줄어들면? 64 → 32 →16 →8 →4 →2 →1
몇 개의 막대기를 합해 input길이가 되는지를 구하는 문제
나머지가 1일 때 count++
예) 23
1 + 2 + 4 + 16 => 총 4회
예) 48
16 + 32 => 총 2회
댓글
댓글 쓰기