백준 - 12931번 : 두 배 더하기 (C++)

풀이 방법 : 그리디

0으로 채워져있는 배열 A 에서 입력으로 주어진 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제다.

처음에는 최소 횟수라길래 반사적으로 BFS를 생각했고 문제에 주어진 연산으로 A에서 B로 바꾸는 모든 경우를 생각하면 경우의 수가 너무 많아져 시간초과가 될 것 같았다.
반대로 연산을 적용하면 모든 수가 짝수인 경우에만 나누기 연산을 해주면 되니까 B에서 A로 가는 최소 횟수를 구하는게 더 나을 것이라 생각했다.

그 생각까지 미치니 그러면 B의 현재 상태에서 홀수인 요소들을 다 -1씩 해줘서 모든 요소들을 짝수로 만든 상태에서 다 2씩 나눠주는 경우가 결국에는 최소 횟수가 될 것이라고 생각하게 됐다.
이를 반복하다가 모든 배열의 요소가 0이 되는 순간 루프를 종료하고 횟수를 출력해주었다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> vecNum(N);
	for (int i = 0; i < N; ++i)
		cin >> vecNum[i];

	int Cnt = 0;
	while (true)
	{
		bool IsEnded = true;

		for (int i = 0; i < N; ++i)
		{
			if (vecNum[i] % 2 == 1)
			{
				--vecNum[i];
				++Cnt;
			}
		}

		for (int i = 0; i < N; ++i)
		{
			if (vecNum[i] != 0)
			{
				IsEnded = false;
				vecNum[i] /= 2;
			}

		}

		if (IsEnded)
			break;

		++Cnt;
	}

	cout << Cnt;
}