[Boj] 백준 C++ #12931 두 배 더하기

📍 문제 링크 : https://www.acmicpc.net/problem/12931

 

📍 알고리즘 분류 : 그리디

 

📍 문제 풀이

반대로 생각하면 된다. 0으로 된 배열 A에서 시작하지 말고, 주어진 배열 B를 0으로 만드는 것이다.

로직은 아래와 같다.

while(모든 원소가 0일때까지){
    for(배열 속 원소들을 하나씩 순회){
        홀수일 경우 1을 빼주고, 연산횟수 카운트
        0이면 0을 따로 카운트
    }
    for(배열 속 원소들을 하나씩 순회){
        //남은 원소들은 모두 0 아니면 짝수이므로
        원소를 2로 나누기
    }
    연산횟수 카운트++;
}

 

 

📍 소스 코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n; cin>>n;
    vector<int> arrB(n,0);
    for(int i = 0;i<n;i++){
        cin>>arrB[i];
    }
    int calCnt = 0;
    int zeroCnt = 0;

    while(zeroCnt != n){
        zeroCnt = 0;
        for(int i=0;i<n;i++){
            if(arrB[i] % 2 == 1){ // 홀수면
                arrB[i]--;
                calCnt++;
            }else if(arrB[i]==0){ // 0이면
                zeroCnt++;
            }
        }
        if(zeroCnt != n){
            for(int i=0;i<n;i++){
                arrB[i] /= 2;
            }
            calCnt++;
        }
    }
    if(calCnt != 0){
        calCnt--;
    }
    cout<<calCnt<<endl;
}

 

마지막에 배열의 모든 원소가 0인 상태에서 한 번 더 모든 원소를 2로 나누는 불필요한 연산 과정이 일어난다.이때 calCnt가 정답보다 1 더 증가한다.

따라서 답이 0인 경우를 제외하고는 마지막에 calCnt에서 1을 빼준 뒤 출력하였다.

 

 

그저께 내가 너무 못해서 현타가 왔는데 .. 골드라는 점에서 자존감을 올려주는 문제였다 ... ㅜ ㅜ