[백준 1052번 C/C++] 물병

 

[백준 1052번 C/C++] 물병

 

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

---

 

 

해결전

 

수학
그리디 알고리즘
비트마스킹

 

각 물병은 서로 다른 물병과 합쳐질 수 있다. 이 합치는 과정은 물병의 2진수로 표현한다.

• 예를 들어, 물병 3개(2진수로 11)를 2개씩 합치면 2진수 100이 되어 물병 1개가 된다.

 

물병을 모두 합쳐서 k개의 물병 이하로 만들어야 한다.

• n이 k보다 작거나 같으면 추가 물병이 필요 없으므로 0을 반환합니다.
• 비트마스킹
  • n의 2진수 표현에서 1의 개수는 현재 물병의 수가 어떻게 조합될 수 있는지를 나타낸다.
    • int BitCnt(int x)
  • n의 2진수 표현에서 1의 개수가 k보다 많으면, 물병을 추가하여 이 개수를 줄여야 한다. 이를 위해 n을 하나씩 증가시키면서 1의 개수가 k 이하가 될 때까지 반복한다.
    • while( BitCnt(temp) > k )

---

 

 

정답코드

 

#include <iostream>
using namespace std;
 
int n, k;	// n: 현재 물병 수, k: 하나로 만들 수 있는 물병의 최대 수
int answer; // 필요한 추가 물병 수
 
// 주어진 정수 x의 2진수 표현에서 1의 개수를 세는 함수
int BitCnt(int x)
{
	int cnt = 0; // 1의 개수를 세기 위한 변수
 
	while(x)
	{
        cnt += (x & 1);  // x의 마지막 비트가 1이면 cnt를 증가
        x >>= 1;  		 // x를 오른쪽으로 1비트 이동
	}
 
	return cnt;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> k;
 
	if (n <= k){	 // 현재 물병 수가 k 이하이면 추가 물병이 필요 없으므로
		cout << "0"; // 0을 출력
		return 0;
	}
	
	int temp = n;
	while (BitCnt(temp) > k) // temp의 2진수 표현에서 1의 개수가 k보다 많으면
	{
		temp++;
		answer++; // 필요한 추가 물병 수를 1 증가
	}
 
	cout << answer;
 
	return 0;
}

---

 

 

코드 비교 

 

주어진 정수 x의 2진수 표현에서 1의 개수를 세는 함수

비트마스킹 형태의 표기

int BitCnt(int x)
{
    int cnt = 0; // 1의 개수를 세기 위한 변수
    
    while(x)
    {
        cnt += (x & 1);  // x의 마지막 비트가 1이면 cnt를 증가
        x >>= 1;  		 // x를 오른쪽으로 1비트 이동
    }
    
    return cnt;
}

 

다른 버젼

int BitCnt(int x)
{
	int cnt = 0; // 1의 개수를 세기 위한 변수
 
	while(x)
	{
		if (x % 2 != 0){ // x를 2로 나눈 나머지가 1이면 (즉, x의 현재 비트가 1이면)
			cnt++;	 	 // 1의 개수 증가
		}
 
		x /= 2;
	}
 
	return cnt;
}

 

---