백준 12931번 두 배 더하기

문제 링크입니다: https://www.acmicpc.net/problem/12931

B 배열을 전부 0인 배열로 바꾼다는 생각으로 거꾸로 접근하면 수월하게 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 배열의 모든 요소를 살피면서 모두 2로 나누어 떨어지는지 확인합니다.

i) 모두 2로 나누어 떨어진다면 우선 전부 2로 나눕니다.

ii) 하나라도 2로 나누어 떨어지지 않는다면 해당 요소를 1 감소시킵니다.

2. 전부 0이라면 A 배열이 된 것이기 떄문에 0을 반환합니다.

3. 1번과 2번을 반복문 내에서 처리하여 총 연산 횟수를 구합니다.

위와 같이 그리디하게 접근한 이유는 1씩 더하는 것보다 2를 곱하는 것이 더 빠르다는 것이 자명하기 때문입니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 50;

 

int N;

int B[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> B[i];

       

        int result = 0;

        while (1)

        {

                 bool allZero = true;

                 bool increment = false;

 

                 for (int i = 0; i < N; i++)

                 {

                         if (B[i])

                                 allZero = false;

 

                         //2로 나누어 떨어지지 않으면 1을 빼준다

                         if (B[i] % 2)

                         {

                                 result++;

                                 increment = true;

                                 B[i] -= 1;

                         }

                 }

 

                 if (allZero)

                         break;

 

                 //전부 2로 나누어떨어질 경우 다 2로 나누어준다

                 if (!increment)

                 {

                         for (int i = 0; i < N; i++)

                                 B[i] /= 2;

                         result++;

                 }

        }

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~