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

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;

    cin >> n;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int zero;
    while(1) {
        zero = 0;
        for (int i = 0; i < arr.size(); i++) {

            if (arr[i] % 2 == 1) {
                ans++;
                arr[i]--;
            }
            if (arr[i] == 0) {
                zero++;
            }

        }

        if (zero == n) {
            break;
        }

        for (int i = 0; i < arr.size(); i++) {
            arr[i] /= 2;
        }
        ans++;
    }

    cout << ans;

    return 0;
}

1. 문제

처음에 0이 n개가 담긴 배열이 있다. 이를 다음 두 연산을 통해 목표 배열로 만들려고 한다.

• 배열에 있는 값 하나를 1 증가시킨다.
• 배열에 있는 모든 값을 두 배 시킨다.

n개의 원소로 이루어진 목표 배열이 주어졌을 때, 처음 배열에서 목표 배열로 만드는 데 필요한 연산 횟수의 최솟값을 구하라.

2. 풀이

처음 배열에서 목표 배열로 갈 수 있다면 반대로 목표 배열에서 첫 배열로 갈 수 있다. 

    int zero;
    while(1) {
        zero = 0;
        for (int i = 0; i < arr.size(); i++) {

            if (arr[i] % 2 == 1) {
                ans++;
                arr[i]--;
            }
            if (arr[i] == 0) {
                zero++;
            }

        }

        if (zero == n) {
            break;
        }

        for (int i = 0; i < arr.size(); i++) {
            arr[i] /= 2;
        }
        ans++;
    }

우선 zero 변수를 선언하여 현재 배열에 있는 0의 개수를 센다. 각 배열을 돌면서 배열의 개수가 홀수이면 1을 더하는 연산을 반드시 해야 하므로 반대로 1을 빼고, 연산 횟수를 증가시킨다. 그러면서 0의 횟수를 센다.

 위 연산에서 모든 홀수에 대해 1을 빼어 짝수를 만들었으므로 모든 배열에 대해 2로 나누는 연산을 하고 연산 횟수를 증가시킨다.

 0의 개수가 n이 되었다면 처음 배열을 만드는 데 성공했으므로 연산 횟수를 출력하고 프로그램을 종료하면 정답을 구할 수 있다.