백준 #1094 막대기

막대기란 문제는 알고리즘을 설명하고, 그 결과를 예측해야 합니다.  사실 여기서 설명하는 알고리즘은 복잡해보이지만, 그것이 무엇을 의미하는지 알면 손쉽게 문제를 풀 수 있습니다.  64와 절반으로 자른다라는 의미만 잘 이해한다면, 쉽습니다.  난이도는 Silver V이지만, 그보다 더 낮아져야 맞을 듯 합니다.

 

 

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

1094번: 막대기

 

어떤 수이든 2진수로 표현할 수 있습니다.  예를 들어서 40이란 숫자를 2의 멱승수로만 표현한다면, $40=32+8$ 로 표현됩니다.  64를 절반씩 잘라나가면, 2의 멱승수가 됩니다.  40을 2진수로 표현하면 10100 이 되겠죠.  5번째 비트는 32가 되고 3번째 비트는 8이 됩니다.  그리고 이 문제는 결국 몇개의 막대기가 필요한가이니까요.  물론 40을 16+16+8로 표현할 수도 있습니다.  하지만 가장 짧은 것을 반으로 잘라야 한다는 것때문에 64를 반으로 자르면 32, 32가 되는데, 하나를 버리고 남은 막대기의 합이 원래수보다 크면 절반 하나를 버리게 됩니다.  그런데 32는 작은 수이기 때문에, 다음으로 32를 16, 16으로 놓게 되겠죠.  32+16이 40보다 크므로 16은 버려야 합니다.  그래서 위와 같이 16+16+8로는 표현을 할 수 없습니다.  그래서 최소의 막대기 갯수와 같은 표현도 필요없게 된 것이죠.

 

결국 2진수로 표현했을 때, 1인 비트의 갯수가 정답이 됩니다.

 

제가 짠 소스는 다음과 같습니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1094 - Bar
//    - by Aubrey Choi
//    - created at 2019-07-03
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, c;
  scanf("%d", &n);
  for(c=0;n;c+=n&1,n>>=1);
  printf("%d\n", c);
}