[그리디] BOJ 12931 두 배 더하기 (C++)

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

12931번: 두 배 더하기

 

문제 해결 알고리즘

 

그리디 알고리즘 문제

 

수 중에 홀수가 존재하면 홀수들을 전부 -1 해준다.

수 중에 홀수가 존재하지 않다면 모든 수를 2로 나눠준다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, result = 0;
int arr[51];

bool is_zero(){

    bool flag = true;

    for(int i=0;i<N;i++){
        if(arr[i]) {
            flag = false;
            break;
        }
    }

    return flag;
}

int main(){
    cin >> N;
    
    for(int i=0;i<N;i++) cin >> arr[i];
    
    while(1){

        if(is_zero()) {
            cout << result;
            break;
        }

        bool div_exist = true;
        for(int i=0;i<N;i++) {
            if(arr[i]%2){
                div_exist = false;
                break;
            }
        }

        if(div_exist){
            for(int i=0;i<N;i++){
                arr[i] /= 2;
            }
            result++;
        }
        else{
            for(int i=0;i<N;i++){
                if(arr[i]%2){
                    result++;
                    arr[i]--;
                }
            }
        }


    }
    
}