12931 두 배 더하기

Link

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

Detail

0인 배열을 만들어서 목표치를 만드는 것과 역산하는 것이 같다고 판단 되어, 입력배열을 0으로 만드는 문제로 재 해석했다.

단순하게 생각해서, 연산횟수의 최소화가 목표라면 반으로 나누는 행위를 최대한 많이 반복하면 된다. 각 원소의 값을 홀수라면 1씩 빼서, 반으로 나누는 연산을 최대한 활용하면 답을 구할 수 있다.

N이 50이하 이므로 반으로 나누는 연산 없이 1000번 빼더라도 시간초과는 나지 않는다.

Code

#include<bits/stdc++.h>
 
using namespace std;
 
int N;
vector<int> A;
 
bool is_full_zero() {
    for(int x : A) {
        if(x != 0) return false;
    }
    return true;
}
 
int solution() {
   int ret = 0;
 
   while(not is_full_zero()) {
        for(int i = 0; i < N; i++) {
            if(A[i] % 2 == 1) {
                A[i]--;
                ret++;
            }    
        }
 
        if(is_full_zero()) break;
        
        for(int& i : A) {
            i /= 2;
        }
        ret++;
   } 
 
   return ret;
}
 
int main() {
    cin >> N;
    A.resize(N);
    for(int& x : A) cin >> x;
 
    cout << solution() << endl;
}