[Python 3] BOJ 12931 두 배 더하기

[English Translation]

There is an array length of N filled wih zeros, named A. Young-sun can do two types of calculations.

• Increment by 1 on one value of the array
• Multiply every values by 2

If array B is given, Make a program that calculates least amount of calculations that have to be made, in order to make array A into B.

 

[Input]

In the first line, size of array N is given. 

In the second line, elements of array B is given divided by blank. Every value in the array B is bigger than or equal to 0 , and smaller than or equal to 1000.

 

[Output]

In the first line, return the least amount of counts that can change array A into array B.

 

n=int(input())
data=list(map(int,input().split()))
count=[[0,0] for _ in range(n)]
for i in range(n):
    while data[i]>0:
        if data[i]%2==0:
            data[i]//=2
            count[i][0]+=1
        else:
            data[i]-=1
            count[i][1]+=1
answer1=0
answer2=0
for i in range(n):
    answer1=max(answer1,count[i][0])
    answer2+=count[i][1]
print(answer1+answer2)

 

count 배열을 통해서 2로 나누기와 -1을 하는 연산 두 종류가 몇 번 필요한지 저장한다.

 

예시를 들어보자.

 

[8,7,6] 이라는 배열을 만들어보자.

먼저 짝수라면 2로 나누고, 홀수라면 1로 나누어보자.

다음과 같이, 2로 나누는 연산이 각각 3, 2, 2번, 1을 빼는 연산이 1, 3 ,1번 이루어졌다.

그 말은 즉슨, 2로 곱하는 연산은 총 3번 이루어져야 해당 결과를 만들어낼 수 있고, 1을 더하는 연산은 총 5번 이루어져야 한다는 뜻이다.

 

다음과 같은 방식으로 연산이 이루어지면 된다.

즉, 1 더하기가 필요한 연산의 수와  2 곱하기 연산이 제일 많이 필요한 element의 2 곱하기 연산의 수를 더하면 정답이 된다.