[BOJ] 1094 막대기

1. 기본 풀이

---

다른것보다 문제를 이해하는데에 시간이 오래걸렸다. 문제만 이해한다면 그냥 시키는 대로만 하면 풀 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int n, num = 64;
    vector<int> v;
    cin >> n;
    v.push_back(64);

    while(num > n) {
        int min = v[0];
        int min_idx = 0;
        for(int i = 0; i < v.size(); i++) {
            if(min > v[i]) {
                min = v[i];
                min_idx = i;
            }
        }
        v.erase(v.begin() + min_idx);
        v.push_back(min / 2);
        num -= min / 2;
        if(num < n) {
            v.push_back(min / 2);
            num += min / 2;
        }
    }

    if(num == n) cout << v.size() << endl;
    else cout << -1 << endl;

    return 0;
}

이해하지 못한 이유

이해를 못한 부분은 1-2.
위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
이 부분인데 처음 64에서 절반 중 하나를 버리고 나머지 하나를 버리면 0인데 뭐 어쩌라는 거지라는 생각을 계속 했다. 이 부분 때문에 구글링도 했는데 나랑 비슷한 사람이 은근 있더라...
어쨌든 저 부분을 풀어서 설명하자면
위에서 자른 절반의 막대와 그 외의 나머지 막대의 길이의 합이 X보다 작으면 절반의 막대 두 개를 그대로 챙기고, 크거나 같다면 둘 중 하나를 버린다는 뜻이다.
즉, 막대의 길이의 합이 X보다 작다면 자르기만 하고 둘 다 챙긴다는 뜻이다.

2. 또 다른 풀이

---

문제를 풀고난 이후 태그를 봤는데 비트마스킹을 봤다. 그래서 왜 이 문제가 비트마스킹인가? 에 대해서 생각해봤다.
이 문제는 기본 막대기의 크기가 (64) ((1000000 == 2^6))으로 주어져있다.
그리고 항상 2씩 나누면서 버릴지 유지할지를 결정한다.

예를 들어보자. 백준에 기본적으로 제시되어 있는 예시인 23을 해보자.

64를 2로 나누면 32. 32는 23보다 크니 버림.

32를 2로 나누면 16. 16은 23보다 작으니 유지

16을 2로 나누면 8. 16 + 8은 23보다 크니 버림.

8을 2로 나누면 4. 16 + 4는 23보다 작으니 유지.

4를 2로 나누면 2. 16 + 4 + 2는 23보다 작으니 유지.

2를 2로 나누면 1. 16 + 4 + 2 + 1은 23과 같다.

결론적으로 23 = 16 + 4 + 2 + 1. 어딘가 익숙한 숫자다.

즉, 항상 2로 나누기 때문에 결과값은 입력값의 비트 개수다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int x;
    cin >> x;
    cout << bitset<7>(x).count() << endl;
    return 0;
}

---

여담으로 이 포스팅은 처음으로 마크다운으로 작성되었다.