[백준 1052번] 물병 (C++)

문제링크 : https://www.acmicpc.net/problem/1052

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K;

int main() {
    int N, K;
    cin >> N >> K;

    int add = 0;
    while (__builtin_popcount(N) > K) {
        N++;
        add++;
    }

    cout << add;
    return 0;
}

 

먼저 1~10까지 직접 그려보며 규칙을 찾아보았다.

2
1 1 -> 2 (10)

3
1 1 1 -> 2, 1 (11)

4
1 1 1 1 -> 2, 2 -> 4 (100)

5
1 1 1 1 1 -> 2, 2, 1 -> 4, 1 (101)

6
1 1 1 1 1 1 -> 2, 2, 2 -> 4, 2 (110)

7
1 1 1 1 1 1 1 -> 2, 2, 2, 1 -> 4, 2, 1 (111)

8
1 1 1 1 1 1 1 1 -> 2, 2, 2, 2 -> 4, 4 -> 8 (1000)

9
1 1 1 1 1 1 1 1 1 -> 2, 2, 2, 2, 1 -> 4, 4, 1 -> 8, 1 (1001)

10
1 1 1 1 1 1 1 1 1 1 -> 2, 2, 2, 2, 2 -> 4, 4, 2 -> 8, 2 (1010)

 

이를 보면 2의 제곱 수에 대해서는 1개의 병만 있으면 되며, 나머지 병의 개수를 보면 2의 제곱으로 이루어진 것을 볼 수 있다.

따라서 이를 2진법으로 표현이 가능하며, 마지막 병의 개수가 2진법에서 1의 개수인 것을 알 수 있다.

따라서 1차적으로 입력받은 N에 대해 2진법으로 바꾸고 1의 개수를 체크하여 K보다 작거나 같다면 정답이다.

 

이제 K보다 큰 경우이다.

K보다 크면 이제 이진법에 1을 더해주며 물병의 개수를 추가해준다.

이진법에서 1을 계속 더해주면 결국 1이 사라지고 0으로 바뀌므로, K값 보다 작은 물병의 개수를 알 수 있다.

위 과정을 반복하며 더해준 총 물병의 개수가 우리가 찾는 정답이 된다.

 

검색을 통해 간단한 함수를 알게 되었는데, gcc 의 내장 함수인 __builtin_popcount(N) 함수를 통해 간단하게 입력받은 N에 대한 이진법 1의 개수를 찾는 것이 가능하다.

또한 C++20의 경우 popcount(N) 표준 함수를 통해 구할 수 있다는 것 또한 알았다.

 

이를 다르게 표현하면, 직접 & 연산을 통해 1을 체크하고, 자릿수를 밀면서 1의 개수를 모두 체크해주면 된다.

int add = 0; //더해지는 수 (추가 물병 수)
while(1)
{
    int cnt = 0; //1의 개수 카운팅
    int tmp = N;
    while(tmp)
    {
        cnt += tmp&1; //현재 1 체크
        tmp >>= 1; //밀면서 전부 체크
    }

    if(cnt <= K) break; //조건 체크
    N++; //1 더해주기 (물병 추가)
    add++;
}