[백준 12931번] 파이썬- 두 배 더하기

백준 12931 - 두 배 더하기

시간 제한 2초, 메모리 제한 512MB

# 조건

• 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다.
• 영선이는 다음과 같은 두 연산을 수행할 수 있다.
  • 배열에 있는 값 하나를 1 증가시킨다.
  • 배열에 있는 모든 값을 두 배 시킨다.
• 배열 B가 주어졌을 떄, 배열 A를 B로 만들기 위한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 배열의 크기 N이 주어진다.(1<=N<=50)
• 둘째 줄에는 배열 B에 들어있는 원소가 공백으로 구분해서 주어진다.
• 배열에 B에 들어있는 값은 0보다 크거나 같고, 1000보다 작거나 같다.

출력

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

# 접근 방법

• 배열 A를 B로 만들려고 하면, 모든 원소를 B와 계속 비교하는 조건문을 달아주어야 한다.
• 따라서 B의 모든 원소를 0으로 만드는 것이 편하다고 생각한다.
• while True:
  • 모든 원소가 0일 때까지 반복문을 돌려주기 위하여 첫 번째 조건문으로 any를 사용해주었다.
  • any는 하나의 원소라도 True가 있으면 True를 반환한다.
  • 즉, 모든 원소가 0이라면 False를 반환하므로 if not any(arrB)인 경우 종료해준다.
• 이후 arrB의 원소를 순회하며 홀수인 경우 -1을 하고 cnt += 1을 해준다.
• 또한, 1보다 큰 경우 => 이미 홀수는 짝수가 되었으므로 고려 x
  • 2로 나눠주며 flag를 True로 변경해준다.
• 1바퀴를 모두 돈 후, flag가 True라면 cnt += 1을 해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
arrB = list(map(int, input().split()))
arrA = [0] * N

cnt = 0
while True:
    if not any(arrB):
        print(cnt)
        break
    flag = False
    for i in range(N):
        if arrB[i] % 2:           
            arrB[i] -= 1
            cnt += 1
        if arrB[i] > 1:
            arrB[i] //= 2
            flag = True
    if flag:
        cnt += 1