[백준,c++] 1094번 - 막대기

문제

1094번: 막대기

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int X; cin>>X;
    int sum = 0;
    vector<int>piece;
    piece.push_back(64);
    
    if(X==64){
        cout<<1;
        return 0;
    }
    while(true){
        sort(piece.begin(),piece.end());
        for(int i:piece) sum+=i;
        if(sum==X) break;
        if(sum>X){
            int half = piece.front()/2;
            if(sum-half>X){
                piece.erase(piece.begin());
                piece.push_back(half);
            }
            else{
                piece.erase(piece.begin());
                piece.push_back(half);
                piece.push_back(half);
            }
        }
        sum=0;
    }
    cout<<piece.size()-1;
}

 

풀이(40분)

이번에도 구현 시간은 7분도 채 되지 않았지만 문제를 이해하는데 30분 걸렸다. 멍청한 게 확실하다.

 

위와 같은 방식으로 문제에서 막대를 자르고, 정석으로 똑같이 구현했습니다. 다만 알고리즘 분류를 보니 수학이었고, 다른 사람들의 풀이를 보니 정말 간단하게 다들 구현했습니다. 이 글을 보는 사람들은 다른 사람들의 풀이를 보는 것을 추천드립니다.