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

문제

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

1094번: 막대기

코드

내 풀이(직관적 풀이)

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int x;
  vector<int> v;
  cin >> x;

  int stick = 64;
  v.push_back(stick);
  if(x!=64){
    while(true){
      stick/=2;
      v.pop_back();
      v.push_back(stick);
      v.push_back(stick);
      int sum = 0;
      for(int i=0; i<v.size()-1; i++){
        sum+=v[i];
      }
      if(sum>=x) v.pop_back();
      if(sum==x) break;
    }
  }
  cout << v.size();
  return 0;
}

 

다른 풀이(이진법 변환 원리)

#include <iostream>

using namespace std;

int main(){
  int x;
  cin >> x;
  int sum = 0;
  while(x>=1){
    sum += x%2;
    x/=2;
  }
  cout << sum;
  return 0;
}

정리

이진법 변환 원리를 문제와 같이 생각하면 다음과 같다.

예를 들어 23cm막대기는 16+4+2+1을 해서 만들 수 있다. 즉 십진수 23을 이진수 10111로 변환한 것과 같다.

이진수 10111의 각 자릿수를 더하면 몇 개의 막대기로 Xcm를 만들 수 있는지 알 수 있다.

참조

https://luv-n-interest.tistory.com/1048