1094_막대기

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

1094번: 막대기

접근

- 문제를 그대로 구현한다

- 막대길이를 저장하기 위해 vector를 사용한다

- 막대기를 내림차순으로 정렬한다

- 맨 끝의 막대기를 절반으로 자르면서 vector의 크기를 1 늘린다

- 만약 새로 추가된 막대기가 x 보다 크다면 pop_back 한다

 

#include <iostream>
#include <algorithm>
#include <vector>

int main(int argc, const char * argv[]) {
    int sum = 65;
    vector<int> woods;
    //input & build
    scanf("%d", &x);
    woods.push_back(64);
    if(x == 64){
        cout<<1<<endl;
        return 0;
    }
    //simulate
    while(true){

        sort(woods.begin(), woods.end(), comp);
        
        int shortest = woods[woods.size()-1];
        if(shortest/2 > 0){
            woods[woods.size()-1] = shortest/2;
            if(shortest/2 < x){
                woods.push_back(shortest/2);
            }
        }else{
            woods.pop_back();
        }
        
        sum = 0;
        for(int len : woods){
            sum += len;
        }
        if(sum==x){
            break;
        }
    }
    cout<<woods.size()<<endl;
    
        
    return 0;
}

더 간단한 방법

x가 0 보다 클 동안

   -막대기의 길이가 x 보다 크다면 막대기를 절반으로 줄인다

   -그렇지 않다면 x를 길이만큼 감소 시키고 막대기의 갯수를 증가시킨다

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int x;

int main(int argc, const char * argv[]) {
    scanf("%d", &x);
    int len = 64;
    int cnt = 0;
    while(x>0){
        if(len > x){
            len/=2;
        }else{
            cnt++;
            x-=len;
        }
    }
    cout<<cnt<<endl;
}