[C++] 백준 12931번: 두 배 더하기

문제 링크

12931번: 두 배 더하기

문제 요약

배열 A를 배열 B로 바꾸려고 하는데, 두가지 연산을 할 수 있다.
1. A의 값 하나를 1 증가시킨다.
2. A의 모든 값을 두 배 시킨다.
이 때, A를 B로 바꾸기 위한 최소 연산 횟수를 구해야 한다.

접근 방법

A를 B로 바꾸는 조건을 가진 문제들 중에서, 다수의 문제들이 B에서 A로 바꾸는 식으로 접근하면 쉽게 풀리는 경우가 있습니다. 이 문제도 그런 유형입니다.

A의 초기값은 모두 0으로 채워져 있는데, B를 A로 바꾸는 식으로 풀 수 있습니다. B의 값들을 모두 검사해서 홀수인 경우 1 감소시키고, 이후에 0인 값들의 갯수를 세어줍니다. 0이 N개가 된다면 그대로 종료하고, 그렇지 않다면 모든 원소를 2로 나눠줍니다.

마지막으로, 1 감소시킨 횟수와 2로 나눈 횟수를 더해서 출력을 해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;
	vector<int> a(n, 0), b(n);

	for (auto& i : b) cin >> i;

	int cnt = 0;
	while (1) {
		int zero = 0;
		for (auto& i : b) {
			if (i % 2) {
				cnt++;
				i--;
			}
			if (i == 0)
				zero++;
		}

		if (zero == n)
			break;

		cnt++;

		for (auto& i : b)
			i /= 2;
	}

	cout << cnt << '\n';
	return 0;
}