[C++] 백준 문제풀이 (Bitmask) 1094번 막대기

 

 

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

1094번: 막대기

 

 

풀이 1.
#include <bits/stdc++.h>


// bitmask[i] 2^i 길이의 막대의 갯수를 의미한다.
int bitmask[7];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    bitmask[6] = 1;
    int x;
    int sum = 64;
    std::cin >> x;

    int ans = 0;

    while(sum != x){
        int i = 0;
        // 가장 짧은 막대를 찾는다.
        while(bitmask[i] == 0){
            ++i;
        }
        if ((sum - (1 << (i - 1))) >= x){
            bitmask[i]--;
            bitmask[i - 1]++;
            sum -= (1 << (i - 1));
        }
        else {
            bitmask[i]--;
            bitmask[i - 1] = 2;            
        }
    }

    for (int i = 0; i < 7; ++i){
        if (bitmask[i]) ++ans;
    }
    std::cout << ans << "\n";
    return 0;
}

풀이2.
#include <bits/stdc++.h>


int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int x;
    std::cin >> x;
    int ans = 0;
    // 2의 거듭제곱꼴의 합으로 x를 나타낼 때, 어떤 거듭제곱이 필요한가에 대한 문제로 생각할 수 있다.
    // 64 = 2^6
    for (int i = 0; i <= 6; ++i){
        if (x & (1 << i)) ++ans;
    }

    std::cout << ans << "\n";
    return 0;
}