백준 1052번 물병[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 비트마스킹 + 그리디입니다. 저는 그리디만을 사용해서 풀이했습니다. 납득이 되는 풀이는 사실 비트마스킹을 사용하는 방법인데요. 저는 빙빙 돌아서 그리디만 사용했습니다. 

 

2. 문제풀이

 N개의 물병과 한 번에 들 수 있는 물병의 개수 K가 주어집니다. 물병을 합치는 로직은 결국 이진수의 원리와 같습니다. 물병 안에 차있는 물은 항상 2의 거듭제곱만큼만 채울 수 있죠. 저는 K - 1번의 루프를 통해 N보다 작거나 같은 2의 거듭제곱 중 가장 큰 수를 골라 N에서 빼주었습니다. 이는 K - 1개의 물통에 채울 물을 결정하는 로직입니다. 

 남은 물의 양 X가 2의 거듭제곱이거나 0이면 상점에서 물을 구매할 필요가 없고, 2의 거듭제곱이 아니라면 남은 물의 양보다 큰 2의 거듭 제곱 중 가장 작은 수 Y를 구한 다음 Y - X를 출력하시면 풀이할 수 있습니다.

 

[ 비트마스킹 응용 방법 ]

 물병 안에 물은 2의 거듭제곱만 채울 수 있습니다. 즉, N을 이진수로 표현했을 때, 1의 개수가 K개 이하이면 됩니다. N을 1씩 더해가며 비트가 1인 개수를 세워주는 로직을 구성하여 풀이할 수 있습니다.

 

3. 코드

3 - 1. 그리디만 활용

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, k;

int find2pow(int x) {
    int ret{};
    for(int i = 0; i <= 30; i++) {
        if((1 << i) <= x) {
            ret = 1 << i; 
        }
    }
    return ret;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> k;

    for(int i = 0; i < k - 1; i++) {
        if(n) {
            n -= find2pow(n);
        }
    }

    int cur = find2pow(n);
    
    int ans = (cur == n ? 0 : (cur << 1) - n);
    cout << ans;
}

3 - 2. 비트마스킹 응용

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, k;

int main() {
    fastio(nullptr, false);

    cin >> n >> k;

    for(int cur = n; ; cur++) {
        if(__builtin_popcount(cur) <= k) {
            cout << cur - n;
            return 0;
        }
    }
}

 

4. 제출 결과