[비트마스킹 / BOJ 1094 / C++] 막대기

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

1094번: 막대기

???

좀 충격이었던 문제였다,,,, 문제의 의미를 진짜 곱씹어보며 잘 살펴보자.

 

특히 테스트케이스에서 답이 나오는 과정을 잘 봐보자.

 

일단 내가 푼 코드부터 보여주겠다.

 

문제가 정말 쉽기 때문에 그냥 보고 읽으면서 코드를 짜도 된다.

 

#include <bits/stdc++.h>

using namespace std;

int X;

vector<int> sticks;

void go(){
    int sum = 0;
    for(auto i : sticks) sum+=i; // 현재 막대기 모든 합.
    
    if (sum==X){ // 막대기 합이 X라면 종료.
        return;
    }
    
    if (sum>X){
        
        int pos = (int)sticks.size()-1;
        int mins = sticks[pos];
        sticks.push_back(mins/2);
        
        sticks.erase(sticks.begin() + pos);
        
        
        int midsum = 0;
        for(auto i : sticks) midsum+=i;
        
        if(midsum >= X){
            go();
        }else{
            sticks.push_back(mins/2);
            go();
        }
    }
    
    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> X;
    
    sticks.push_back(64);

    
    go();
    
    cout << sticks.size();
    
}

// 막대길이 다 더해. 합이 X보다 크면 밑에 반복
// 막대길이 중 가장 짧은거 절반으로.
// 절반 막대 하나 버리고, 남은 막대 길이의 합이 X보다 크거나 같다면

//64 -> 32 32 -> 32 -> 16 16  -> 16 8 -> 16 4 4 -> 16 4 2 2 -> 16 4 2 1

문제에 나온 순서대로 보아 재귀적으로 해결했다. 그런데 이  문제 잘보면 뭔가 이상하지 않나???

 

모든 숫자들이 반드시 2의 배수 숫자들과, 1로 표현돼어, 이 숫자들의 개수를 세는 것과 같다.

 

즉, 주어진 숫자를 이진수로 표현할 때, 그때 나오는 1의 개수를 세라는 문제와 같다는 의미이다!!

 

그래서 이 문제를 다시 풀자면, 아래와 같이 간단하게 해결할 수 있다.

(물론 64미만이라는 조건을 달아야겠지만, 그건 뭐 간단하니깐..)

 

#include <bits/stdc++.h>

using namespace std;

int X;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> X;
    int ret=0;
    while (X>0){
        if(X%2){
            ret++;
        }
        
        X=X/2;
    }
        
    cout << ret;
    
    
}