1094 막대기

이 문제 작년에 PS 접하기 전에 풀려다가 어려워서 못푼 거 생각난다 ㅎㅎ

 

암튼.. 막대 붙이는게 복잡해 보이지만 결과적으로 구하는 건 Xcm 막대를 만들기 위해서 2의 제곱 길이의 막대를 몇 개 써야 되냐는 문제로 바꿀 수 있다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    cin >> n;

    int m = 64;
    int count = 0;
    while (n > 0)
    {
        if (n < m)
        {
            m /= 2;
            continue;
        }

        n -= m;
        count++;
    }
    cout << count << endl;

    return 0;
}

 

---

ㅋㅋㅋㅋ 이 문제 다른 방식으로도 풀 수 있다. 

 

2의 제곱 형태의 수를 몇 개를 쓸 수 있나 = 2진법에서 비트를 몇 개 쓸 수 있냐

 

이렇게 생각할 수 있다.

 

그럼 이걸 비트맵을 써서 구할 수 있음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    cin >> n;

    cout << bitset<32>(n).count() << endl;

    return 0;
}

 

ㅋㅋㅋㅋㅋㅋㅋ 비트맵이 이렇게도 쓰이는구나

 

신기해