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

 

12931번: 두 배 더하기

거의 한 달만에 푸는 문제... 변명을 하자면 그간 졸업작품 때문에 정말 정말 정말 바빴다... 어제 학교에서 열리는 e스포츠 대회에 전시할 빌드본 버그를 새벽까지 고치고 주말에 시간이 조금 남아 뒹굴거리다... 언니랑 같이 공부하며 정말 오랜만에 풀어보았다.

 

오랜만에 푸는 거라 알고리즘을 구상하는데 적지 않은 시간이 걸렸지만... 오랜만에 문제 해결하는 고통과 즐거움을 다시 한 번 느꼈다!!

 

 

알고리즘 설계

처음에는 [0, 0, 0...]을 입력받은 배열로 어떻게 만들어야할지 고민했다. 한 요소만 떼어놓고 보자면, 연산 방법은 2를 곱하거나 1을 더하는 것이기 때문에 항상 커질 수밖에 없다.

 

따라서 0부터 가장 작은 한 요소까지 최소 연산 횟수를 구하고 그 과정에서 쓰였던 x2 연산을 다른 요소들에도 적용하고... 그런데 0부터 시작하니 처음엔 무조건 +1이 필요하니...

 

 

이 사고까지 가니 코드가 너무 복잡해지고 조금 더 편리한 방법이 있을 거라는 생각이 들었다. 그래도 떠오른 생각을 구현해보고자, 최소 연산 횟수를 구하는 알고리즘을 생각해냈다.

 

N부터 0으로의 최소 연산 횟수를 구했다. 역행에서 구하니 홀수이면 1을 빼주고, 짝수이면 2로 나누어주었다.

 

ex)
7 (홀수: -1)
6 (짝수: /2)
3 (홀수: -1)
2 (짝수: /2)
1 (홀수: -1)
0

 

이 알고리즘을 구상하며 떠오른 생각. 이거... 배열 전체에도 적용시킬 수 있겠다!

 

 

[0, 0, ...]부터가 아니라, 원래 배열부터 시작해 [0, 0, 0]을 만드는 것이다.

 

1. 배열의 합이 0이 될 때까지.

2. 배열의 요소가 홀수이면 해당 요소를 -1 시킨 후 연산 횟수를 +1

3. 모든 배열의 요소를 2로 나누고 연산 횟수를 +1

 

코드

#include <iostream>
using namespace std;

int arr[50];

int main()
{
    int len, res = 0, sum = 0;
    cin >> len;

    for (int i = 0; i < len; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }

    while (sum)
    {
        for (int i = 0; i < len; i++)
        {
            if (arr[i] % 2 == 1) 
            {
                // 홀수인 수 1 빼기 + 합 갱신
                --arr[i];
                --sum;
                ++res;
            }
        }

        if (sum != 0)
        {
            for (int i = 0; i < len; i++)
            {
                // 모든 수 2로 나누기 + 합 갱신
                sum -= arr[i] / 2;
                arr[i] /= 2;
            }

            res++;
        }
    }

    cout << res;
}

 

오랜만에 풀어서 구상이 조금 걸렸던 문제... BIC나 GIGDC에 제출할 때까지 꾸준히 풀지는 못하겠지만... 그래도 너무 소홀히 하지는 말아야겠다!