[BOJ/12931/C++] 두 배 더하기

이번에 푼 문제는 "두 배 더하기"이다.

문제에서는 배열 A를 배열 B로 만들기 위한 연산의 최소 횟수를 구하라고 하였다.

 

그래서 당연히 배열 A를 B로 만들기 위한 최소 연산 과정을 고민하였다.

 

그러나 이렇게 푸는 것보단 배열 B를 배열 A로 만드는 것이 더 효율적이라는 것을 깨달았다.

그렇게 된다면 계산 과정은 반대가 될 것이다.

• 배열에 있는 값 하나 1 빼기
• 배열에 있는 모든 값을 2로 나누기

그리고 배열에 있는 모든 숫자가 0이 되면 배열 A를 만든 것이기 때문에 성공한 것이다.

 

문제 로직은 다음과 같다.

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
    int N, tmp;
    int count = 0;
    cin >> N;

    vector<int> B;

    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        B.push_back(tmp);
    }

    while (true)
    {
        int zero = 0, even = 0;
        for (auto& i : B)
        {
            if (i % 2 != 0)
            {
                count++;
                i--;
            }
            else  even++;
            if (i == 0)  zero++;
        }

        if (zero == N) break;

        if (even == N)
        {
            count++;
            for (auto& i : B) i = i / 2;
        }
    }

    cout << count;

    return 0;
}

 

when문을 도는 도중 모든 값이 0이면 (=A배열이 되면) break를 이용해 반복문 탈출하는 것이다.

이때 when문에서 사용할 변수는 2가지이다.

• zero : 모든 값이 0인지 계산함
• even : 모든 값이 짝수인지 계산함

계산을 수행할 때마다 count라는 변수를 증가시켜 최종적으로 출력하면 된다.