[백준 12931번] [그리디] 두 배 더하기

어렵지는 않은 문제이다.

풀이방법은 다음과 같다.

1. Compare array에서 1을 가장 최우선적으로 체크한다.
(1은 바로 0으로 만들면 연산을 아얘 안할 수 있개 때문이다.)
2. 0과 1이 아닌 원소를 고려하되, 짝수 홀수를 판단하여 홀수면 1개 줄이고 2로 나눠준다.
(홀수라는 것은 해당 단계에서 +1을 해줬다는 의미이다. 왜냐하면 만약 그렇지 않다면 x2되어 짝수가 나오게 된다.)

위의 내용을 보면 그리디 알고리즘이라는 것을 인식해야 한다.

부분적으로

1. 1을 찾는다.

2. 0과 1이 아닌 수 중에 홀수면 -1시키고, 짝수면 그대로 납둔 상태에서 1/2시킨다.

3. 변경된 숫자들을 가지고 1, 2 과정을 반복한다.

 

즉, 초기 compare array에서 최적해를 다시 1, 2 과정으로 다시 최적화를 함으로써 정답에 가까워지는 형태이므로

탐욕적 선택 속성(Greedy choice property)를 가지고 있음을 알 수 있다. 따라서 위 문제는 최적 부분 구조(Optimal substructure)이다.

 

이 내용을 파악하고 그리기 기법을 활용하여 문제를 풀었어야 한다.

 

그리디 알고리즘의 경우, 단순히 푸는 것에 만족하지 말고 

최적 부분 구조를 만족한다는 것을 증명하고 접근하는 자세를 익히는 것이 훨씬 더 중요하다고 할 수 있겠다.

 

위의 내용을 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;
    vector<int> compare_store(N, 0);

    for(int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        compare_store[i] = temp;
    } // Compare data_store

    int count = 0;

    while(true){
        bool check = false;
        bool zero_check = true;
        for(int i = 0; i < N; i++){
            if(compare_store[i] == 1){
                count += 1;
                compare_store[i] = 0;
                zero_check = false;
            }
            else if(compare_store[i] == 0);
            else if(compare_store[i] % 2 == 1){
                count += 1;
                compare_store[i] -= 1;
                compare_store[i] /= 2;
                zero_check = false;
                check = true;
            }
            else{
                compare_store[i] /= 2;
                zero_check = false;
                check = true;       
            }
        }
        if(check == true){
            count += 1;
        }
        if(zero_check == true) break;
    }

    cout << count << "\n";
    return 0;
}