[BOJ-1094]막대기

간단한 시뮬레이션 구현문제

#include<cstdio>
#include<vector>
#define pb(a) push_back(a)
using namespace std;
typedef vector<int> vi;
vi v;
 
int stick_sum(){
    int ret = 0;
    for(int i = 0  ; i < v.size() ; i++)        ret += v[i];
    return ret;
}
 
int main(){
    int x; scanf("%d", &x);
    v.pb(64);
    while(1){
        if(stick_sum() == x) break;        
        int small = v[v.size()-1];
        v.erase(v.begin()+v.size()-1);
 
        if(small > 1){
            small = small >> 1;
            v.pb(small); // 자른 막대의 절반 중 하나를 버리고
            // 남아있는 막대의 길이의 합이 x보다 크다면 버린상태로
            if(stick_sum() < x) v.pb(small); // x보다 작다면 막대를 버리지 않음.
        }
    }
    printf("%d", v.size() );
    return 0;
}