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

• Problem Link : https://www.acmicpc.net/problem/12931

문제

모든 원소가 0인 배열을 특정 과정을 최소로 몇 번 반복해여 입력 배열로 만들 수 있는지 구하여라.

입력

• 첫째 줄, 배열의 크기 N이 주어진다.
• 둘째 줄, 배열 B에 들어있는 원소가 주어진다.

출력

배열 A를 B로 바꾸기 위한 최소 연산 횟수를 출력한다.

풀이

[0, 0, 0 ... ]부터 시작해서 입력에 들어오는 배열을 만드는 것보다는 입력으로 들어온 배열을 [0, 0, 0]으로 만드는 과정이 간단할 것이기 때문에 해당 방식으로 진행한다.

왜 거꾸로 하는 과정이 간단하자면 [0, 0]에서 3번의 과정을 거쳐서 나오는 배열은 [3, 0], [0, 3], [2, 1], [1, 2], [4, 0], [4, 0] 과 같이 많은 배열이 나오기 때문에 과정을 수행하면서 많은 경우의 수가 발생한다.
이 과정을 거꾸로 한다면 굳이 불필요한 경우의 수를 구하는 과정을 제외할 수 있다.

그렇다면 거꾸로 [0, 0, 0 ...] 을 어떻게 만들까? 입력의 배열은 아래와 같은 두 가지 방법으로 생성된다.

1. 원소 하나 +1
2. 모든 원소 *2

이 두 과정을 반대로 수행한다면?

1. 원소 하나 -1
2. 모든 원소 /2

이 때 우선순위는 무조건 2번이다. 최소 횟수를 구하는 것이기 때문에 동시에 많은 수를 작게 만들수록 모든 원소를 0으로 빠르게 바꿀 수 있다.

2번이 왜 무조건 우선순위냐면 원소 하나를 -1하는 것보다 하나 이상의 원소를 2로 나누는 것이 더 많이 배열의 원소들의 총 합을 빠르게 줄일 수 있기 때문이다.

모든 원소를 2로 나눌 수 있다는 뜻은 모든 원소가 짝수여야만 가능하다는 것이다. 따라서 홀수 원소를 모두 1씩 빼준 후에 모든 원소를 2로 나누어주는 과정을 반복하면 된다.

코드

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))

ans = 0
while sum(a) > 0 :
    # remove odd number element in array
    for i in range(len(a)) :
        if a[i] % 2 == 1 :
            a[i] -= 1
            ans += 1

    if sum(a) == 0 : break

    # devide 2 all even number in array
    a = [x / 2 for x in a]
    ans += 1

print(ans)