백준 1052

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

이 문제의 경우 그리디와 비트 마스킹  문제이다 처음에는 while문으로 코드를 작성했으나 해당 문제를 해결 하려했으나 실패 했다. 이에 비트  마스킹을 사용해서 문제를 풀어야 함을 깨달았다. 이 문제를 풀기 위한 생각은 

 

3리터짜리 물병을 생각해 보면 2리터 물병 하나 1리터 물병이 있다고 가정 하자. 얘를  물병 한개짜리를 만드는 방법은 1리터짜리 물병을 하나더해서 2리터짜리를 만든후 4리터 물병을 만드는 방법이다

즉 이문제를 풀기  위해서는 가장 작은 물병들을 계속 그다음 큰 물병들로 만들면서 진행 해야한다 자 대표적인 예로
2번째 테스트 케이스를 예시로 생각해봅시다

이 문제의 경우 0번째  칸에 있는 1리터짜리 물병을 일단 큰물병으로 만들어보자 1+1 해서 2리터로 만든다 그 후 최소 물병과 다른  물병의 갯수를 저장해놓고 일단  계속 가장 작은 물병을 다음 큰 물병으로 변경시켜 가면서 물병을 합치면서 크기를 늘리면서 갯수를 줄이는 로직이다 그후 최소 물병의  갯수를  만족하면 로직진행을 끝내면 된다

#include<bitset>
#include<iostream>
using namespace std;
int main() {
	int n, k;
	int ans=0;
	cin >> n >> k;
	while (true) {
		int temp = n;
		// 현재 1을 못만났다는 의미
		int firstOnidx = -1;
		//  내가  가지고 있는 물병의 갯수
		int cnt=0;
		// 내가 비교하려는 인덱스의 번호
		int idx = 0;
		
		//현재 물병의 수를 세는 로직
		while (temp) {
			if (temp & 1) {
				if (firstOnidx == -1)
					firstOnidx = idx;
				cnt++;
			}
			idx++;
			//다음 번째 인덱스를 비교하기 위해 오른쪽으로 1칸 이동
			temp >>= 1;
		}
		//
		if (cnt <= k) {
			break;
		}
		else {
			//가장 작은 양이 담겨져 있는 물병을 합쳐서 다음  크기의 물병을 만들기 위함 반복하다보면 원래있던 더큰 크기의 물병과 합쳐지면서 크기가 줄어듬
			n += (1 << firstOnidx);
			//산 물병의  갯수 크기2짜리 물병은 1개짜리 물병 2개 합친것
			ans += (1 << firstOnidx);
		}

		
	}
	cout << ans;
}