[백준 12931] 두 배 더하기 (python)

https://www.acmicpc.net/problem/12931

12931번: 두 배 더하기

두 배 더하기 문제

0으로 이루어진 크기 N의 배열 A를 주어진 조건에 맞는 연산을 진행했을 때, B와 같게 만들려면 최소 몇 번 연산을 구하는 문제.

그리디로 접근해서 해결할 수 있었다.

📌문제 접근 포인트

 1. 주어진 연산은 배열의 값 1개를 1 증가 & 전체를 2배 하기의 연산의 과정으로 이루어져 있다. 0으로 이루어진 A배열을 B배열로 만드는 것보단 B배열을 0으로 이루어진 배열로 만드는 것이 더 간단하기 때문에 B를 변형하는 방법으로 진행하자.
2. B를 반대로 만드는 과정을 진행해야 하니 연산을 반대로 생각하자, 즉 배열의 값의 값 1개를 1 감소 & 전체를 2로 나눠주는 연산으로 생각해 보자.
3. 단순하게 생각했을 때, 연산 수를 줄이기 위해서 큰 값을 작게 만들 수 있는 연산을 수행해야 한다. 즉, 전부 짝수로 만들고 -> 전부 짝수면 나눠주는 과정을 반복하면 횟수가 제일 줄어든다는 것을 알 수 있다. 
4. 해당 과정을 반복해서 전부 0이 되도록 구현해 주자.

⚙️내가 푼 정답 코드

import sys
N = int(sys.stdin.readline())
B = list(map(int,sys.stdin.readline().split()))
result = 0
while True: 
    for i in range(N): # 각 값에 대해
        if B[i] % 2: # 홀수면
            B[i] -= 1 # 1을 빼고
            result += 1 # 횟수 + 1
    if sum(B) == 0: # 빼봤더니 전부 0 이면
        break # 끝
    for i in range(N): # 짝수인 애들을
        B[i] /= 2 # 전부 나누고
    result += 1 # 횟수 + 1
print(result)