[G5] 백준 1052번 물병 C++ 그리디 알고리즘, 비트마스킹

리뷰

 

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

문제 지문이 살짝 모호하고, 정답이 0이 나오는 엣지 케이스를 처리하지 못해 계속 Fail을 받았었다.

 

 

전역 변수

• n : 물병의 개수를 저장할 변수
• k : 한 번에 옮길 수 있는 물병의 제한을 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, k에 값을 입력 받고, 변수 cnt, ans를 0으로 초기화 해준다.
2. 31부터 0까지 감소하는 for문을 개행해 준다.
3. 만약 n의 비트가 1을 왼쪽으로 i만큼 쉬프트한 값과 비트가 같을 경우 n에서 1 << i 만큼 빼준다.
4. cnt를 증가시키고, cnt가 k이며 n이 아직 존재할 경우 ans에 1 << i - n의 값을 저장하고 break해준다.
5. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 만약 정답이 없을 경우에는 -1을 출력한다. 라는 의미가 구매할 물병이 없을 경우, 즉 ans가 0일 경우 -1을 출력하라는 것으로 이해했으나 구매할 물병이 없을 경우 그냥 0을 출력해 주면 된다.
2. cnt가 k일 경우만 생각해 줬는데 n이 0일 경우엔 ans는 0인 상태로 유지해야 했다.
3. 따라서 cnt가 k면서 n이 0이 아닐 경우만 ans에 값을 저장하고, ans자체 그대로 출력해 주니 AC를 받았다.

 

참고 사항

• 정답이 없는 경우는 없다.

 

정답 코드

#include<iostream>
using namespace std;

int n, k;

int main() {
	cin >> n >> k;

	int cnt = 0, ans = 0;
	for (int i = 31; i >= 0; --i) {
		if (n & (1 << i)) {
			n -= (1 << i);
			cnt++;
			if (cnt == k && n) {
				ans = (1 << i) - n;
				break;
			}
		}
	}
	cout << ans;
}