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

---

문제 설명

그리드 알고리즘 문제

 

 

 

---

문제 풀이

 

저는 이 문제를 보고 바로 2048게임이 생각났습니다ㅋㅋ

 

이 문제의 규칙은 다음과 같습니다.

2의 거듭제곱마다 하나의 물병으로 만들 수 있습니다.

 

합쳐지지 못한 물병을 세어가며 들고가야하는 물병의 개수가 K보다 작아질 시점을 구하면 됩니다.

 

문제 입력 예시인 

13 2

로 예시를 들어보겠습니다.

 

우리는 i값을 구하면 됩니다.

 

---

코드

#include <iostream>


int main()
{
	int N, K;
	int i = 0;
	
	std::cin >> N >> K;

	while (1)
	{
		int tmp = N; //N을 0이 될 때까지 나누므로 새로 갱신해야 합니다.
		int result = 0; //들고가야 할 물병
		
		while (tmp > 0)
		{
			if (tmp % 2 == 1) //들고가야 할 물병 개수를 구하는 식
				result++;

			tmp /= 2;
		}

		if (result <= K)
			break;
		
		i++;
		N++;
	}

	std::cout << i;
	return 0;
}