[백준/Baekjoon] 1052 물병 C++ :: Bit masking | Greedy

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

1052번: 물병

---

1. Logic

여기서 비트는 한 물병으로 얼마나 물이 모였는지를 나타낸다. 항상 물은 똑같은 양끼리 합칠 수 있고 1부터 시작하기 때문에 1 > 2 > 4 > 8 > 16 등등 이렇게 2의 제곱수로 늘어나게 된다. 즉 1의 갯수는 물이 담긴 물병의 갯수를 의미한다.

 

테스트케이스인 13, 2를 예시로 들어보면 13을 2진수로 변환하면 1101이다. (8 + 4 + 1) 1이 먼저 나오는 위치는 0번째이고 똑같은 양을 더해줘야 하기 때문에 0번째를 한번 더 더해준다(1 << 0). 이렇게 되면 14가 된다. 2진수로 변환하면 1110인데

1의 갯수가 3개이기 때문에 한번 더 이전 과정을 진행해주면 (1<<1)을 해주고 16이 되어 10000 1의 갯수가 1개이기 때문에 조건을 충족하고 답은 1+2 즉 3이 되게 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int ans;
int n, k;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    
    while(true) {
        int temp = n;
        int firstOnIdx = -1;
        
        int cnt = 0;
        int idx = 0;
        while(temp) {
            if(temp & 1) {
                if(firstOnIdx == -1) firstOnIdx = idx;
                cnt++;
            }
            idx++;
            temp >>= 1;
        }
        
        if(cnt <= k) break;
        else {
            n += (1<<firstOnIdx);
            ans += (1<<firstOnIdx);
        }
    }
    
    cout << ans;
}

---

3. Feedback

비트마스킹 너무 어려워,,,!

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐