문제 링크 : https://www.acmicpc.net/problem/1094
문제
지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가
Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.
막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다.
지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.
지민이가 가지고 있는 막대의 길이를 모두 더한다.
처음에는 64cm 막대 하나만 가지고 있다. 이때,
합이 X보다 크다면, 아래와 같은 과정을 반복한다.
가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.
X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.
출력
문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수
있는지 출력한다.
예제
문제를 보자 64를 절반으로 32 16 8 4 2 1... 보이지 않는가? 숫자의 수열이 2진수이다. 그러면 비트연산을 이용하면 쉽게 풀 수 있을 것이다.
첫번째 예제를 보면 23이다. 23을 2진수로 표현하면(64자리 까지 표현 하였다.) 0010111 이다. 아래 사진을 보자
23은 2진수로 64자리까지 0010111 여기서 1을 찾아내면 되니 1은 4개 정답은 4가 나오는 것이다. 그러면 간단하게 for문을 7번 돌며 비트 연산을 하면 쉽게 1을 찾아 낼 수 있을 것이다. 코드를 보자
#include <iostream>
#include <string>
int main()
{
int input = 0; // 사용자 입력 변수
int result = 0; // 답 출력 변수
std::cin >> input; //사용자 입력 받기
for (int i = 0; i < 7; ++i)
{
if (input & (1 << i)) //0010111 &연산으로 1을 왼쪽으로 i만큼씩 증가시킴
{
++result;
}
}
std::cout << result;
}첫번째 if문 부터 차근차근 코드를 살펴보자
첫번째 if문에서는 1을 i(0)만큰 왼쪽으로 쉬프티 연산 시키면 0000001
&연산을 하면 겹치는 곳은 1 부분 밖에 없으니 답은 1로 result값이 증가된다.
이제 똑같이 반복해주면 된다.
input 값 : 0010111 첫번째 if문 값 : 0000001 &연산 : 1 result 값 증가
input 값 : 0010111 첫번째 if문 값 : 0000010 &연산 : 2 result 값 증가
input 값 : 0010111 첫번째 if문 값 : 0000100 &연산 : 4 result 값 증가
input 값 : 0010111 첫번째 if문 값 : 0001000 &연산 : 0 result 그대로
이대로 쭉 반복하다보면 답이 나올 것이다.
답은 4
